Homework 1

CS 243
Homework #1
Theory of Compuation
Fall 2014
Due: 4 pm., Wednesday, Sept. 10, 2014
Unless indicated otherwise, each problem is worth ten points. Students enrolled for graduate credit (including CE enrollment) should also complete the problems marked with a black diamond [⧫]. Undergraduate students may do so for extra
credit. Please show all of your work: unsupported answers will usually receive zero credit.
1. Write down the formal definitions for a DFA, NFA, єNFA, regular language, and regular expression. Each definition should be complete, and grammatically correct. (Note that some authors, like Sipser define єNFA ⊂ NFA,
and others like Hopcroft et al., take NFA ∩ єNFA = ∅. Use the definitions you prefer, but be consistent.)
2. Construct a DFA state diagram that recognizes each of the following languages for the alphabet Σ = {0, 1}.
(a) {0w1 ∶ w ∈ Σ∗ }, that is the strings that begin with 0 and end with 1.
(b) {w ∈ Σ∗ ∶ ∣w∣ ≤ 5}. (N.B. ∣w∣ denotes the length of the string w.)
(c) {w ∈ Σ∗ ∶ ∣w∣1 ≥ 3}. (Here, ∣w∣ a denotes the number of times the letter a appears in string w.)
(d) {x0110y ∶ x, y ∈ Σ∗ }.
(e) {x111 ∶ x ∈ Σ∗ }, i.e., the language of strings that end with 111.
(f ) {є, 0}, (S, p. 84).
(g) The set of strings that do not contain two or more consecutive repetitions of the same letter.
(h) The set of strings such that each block of five consecutive symbols contains at least two 0’s (HMU, p. 53).
(i) The set of strings in which all of the 0’s precede all of the 1’s. (This language includes є, 011, 000, and 111, and
can be described as the language 0∗ 1∗ .)
3. Consider the following DFA:
1
q0
0
q1
1
q2
0,1
0
Represent the language that this automaton recognizes as a regular expression.
4. Construct an єNFA state diagram that recognizes each of the following languages, again assuming that Σ = {0, 1}.
Try to find a representation that minimizes the total number of states.
(a) The language 0∗ 1∗
(b) {є, 0}.
(c) {w ∈ Σ∗ ∶ w neither contains the substring 01 nor the substring 10}.
5. A DFA with two states q 0 , q 1 describes a simple computer with a one-bit memory. Assume Σ = {0, 1}, Without
loss of generality, assume that the start state is q 0 .
(a) How many different languages can such a DFA be programmed to recognize over the binary alphabet Σ?
(b) Is there a two-state DFA that recognizes the language {w ∈ Σ∗ ∶ ∣w∣0 ≥ 1}? Is there one that recognizes the
language {w ∈ Σ∗ ∶ ∣w∣0 ≥ 2}?
(c) Is there a two-state DFA that recognizes a string that ends with a 0? What about a string that ends with 00?
6. [⧫] Approximately how many different languages, using a binary alphabet, can be recognized by a DFA that
contains three states.
August 30, 2014 (12:04 AM)
1
Robert R. Snapp © 2014
7. [S: p. 90] Prove that the following languages are not regular:
(a) 0m 1m 0n ∶ m, n ≥ 0.
(b) {0m 1n ∣m ≠ n},
(c) {w ∶ w ∈ {0, 1}∗ and w is not a palindrome}}.
(d) [⧫] {wtw ∶ w, t ∈ {0, 1}+ }
(It is instructive to compare Problem 7b with 2i.)
8. Prove or disprove: (0∗ 01 ∪ 10)∗ 0∗ = (0 ∪ 01 ∪ 10)∗ ?
August 30, 2014 (12:04 AM)
2
Robert R. Snapp © 2014

Download Report