CS 341: Foundations of Computer Science II Prof. Marvin Nakayama
Homework 3 Solutions
1. Give NFAs with the specified number of states recognizing each of the following lan- guages. In all cases, the alphabet is Σ = {0, 1}.
(a) The language { w ∈ Σ∗ | w ends with 00 } with three states. 0,1
10203
(b) The language { w ∈ Σ∗ | w contains the substring 0101, i.e., w = x0101y for
some x, y ∈ Σ∗ } with five states.
0,1 0,1
102130415
(c) The language { w ∈ Σ∗ | w contains at least two 0s, or exactly two 1s } with six
states.
1
0
0,1 1 0,1 20304
ε
1
516
00
(d) The language {ε} with one state.
1
1
(e) The language 0∗1∗0∗0 with three states. 010
1ε203
2. (a) Show by giving an example that, if M is an NFA that recognizes language C, swapping the accept and non-accept states in M doesn’t necessarily yield a new NFA that recognizes C.
Answer:
The NFA M below recognizes the language C = {w ∈ Σ∗ | w ends with 00}, where Σ = {0, 1}.
0,1 10203
Swapping the accept and non-accept states of M gives the following NFA M′: 0,1
10203
Note that M′ accepts the string 100 ̸∈ C = {w | w does not end with 00}, so
M′ does not recognize the language C.
(b) Is the class of languages recognized by NFAs closed under complement? Explain
your answer.
Answer:
The class of languages recognized by NFAs is closed under complement, which we can prove as follows. Suppose that C is a language recognized by some NFA M, i.e., C = L(M). Since every NFA has an equivalent DFA (Theorem 1.39), there isaDFADsuchthatL(D)=L(M)=C. Byproblem3onHomework2,we then know there is another DFA D that recognizes the language L(D). Since
2
every DFA is also an NFA, this then shows that there is an NFA, in particular D, that recognizes the language C = L(D). Thus, the class of languages recognized by NFAs is closed under complement.
3. Use the construction given in Theorem 1.39 to convert the following NFA N into an equivalent DFA.
ε
12 a
a
3
b
Answer: Let NFA N = (Q,Σ,δ,1,F), where Q = {1,2,3}, Σ = {a,b}, 1 is the start state, F = {2}, and the transition function δ as in the diagram of N. To construct a DFA M = (Q′,Σ,δ′,q0′ ,F′) that is equivalent to NFA N, first we compute the ε-closure of every subset of Q = {1, 2, 3}.
a,b
Set R ⊆ Q
ε-closure E(R)
∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
∅ {1, 2} {2} {3} {1, 2} {1, 2, 3} {2, 3} {1, 2, 3}
Then define Q′ = P(Q), so
Q′ = { ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }.
The start state of M is then E({1}) = {1, 2}. The set of accept states of M is F′ = { {2}, {1,2}, {2,3}, {1,2,3} }.
We define the transitions in the DFA M as in the following diagram:
3
b
{2, 3} a
b
{1,2} a {1,2,3}
b a,b
∅
a
Note that we left out some of the states (e.g., {1}) in P(Q) from our diagram of the DFA M since they are not accessible from the start state {1, 2}. Also, we had to add an arc from state ∅ to itself labelled with “a, b” so that this state has an arc leaving it corresponding to each symbol in the alphabet Σ, which is a requirement for any DFA.
The algorithm given in the notes and textbook will always correctly construct an equivalent DFA from a given NFA, but we don’t always have to go through all the steps of the algorithm to obtain an equivalent DFA. For example, on this problem, we begin by figuring out what states the NFA can be in without reading any symbols. In this case, this is E({1}) = {1,2} since 1 is the starting state of the NFA, and the NFA can jump from 1 to 2 without reading any symbols by taking the ε-transition. Thus, we first create a DFA state corresponding to the set {1, 2}:
{1, 2}
The state {1,2} is the start state of the DFA since this is where the NFA can be without reading any symbols. The state {1, 2} is also an accepting state for the DFA since it contains 2, which is accepting for the NFA.
Now for DFA state {1, 2}, determine where the NFA can go on an a from each NFA state within this DFA state, and where the NFA can go on a b from each NFA state within this DFA state. On an a, the NFA can go from state 1 to state 3; also, the NFA can go from state 2 to 1, and then it also can go further from 1 to 2 on the ε. So from NFA states 1 and 2 on an a, the NFA can end up in states 1, 2, and 3, so draw a transition in the DFA from state {1, 2} to a new state {1, 2, 3}, which is an accepting state since it contains 2 ∈ F :
4
{1,2} a {1,2,3}
Similarly, to determine where the DFA moves on b from DFA state {1, 2}, determine all the possibilities of where the NFA can go from NFA states 1 and 2 on b. From state 1, the NFA can’t go anywhere on a b; also, the NFA can’t go anywhere from state 2 on b. Thus, the NFA can’t go anywhere from states 2 and 3 on a b, so we add a b-edge in the DFA from state {1, 2} to a new DFA state ∅, which is not accepting since it contains no accept states of the NFA:
{1,2} a {1,2,3} b
∅
Now every time we add a new DFA state, we have to determine all the possibilities of where the NFA can go on an a from each NFA state within that DFA state, and where the NFA can go on a b from each NFA state within that DFA state. For DFA state {1, 2, 3}, we next determine where the NFA can go on an a from each of the NFA states1,2and3. FromNFAstate1,theNFAonanacangotoNFAstate3;from NFA state 2, the NFA on an a can go to NFA state 1, and then it can also further jumpto2onε;fromNFAstate3,theNFAonanacangotoNFAstate2. Thus,if the NFA is in states 1, 2 and 3, it can go on an a to states 1, 2 and 3, so we add to the DFA an a-edge from {1, 2, 3} to {1, 2, 3}.
{1,2} a {1,2,3} b
∅
a
Now we determine where the b-edge from DFA state {1,2,3} goes to. To do this, we examine what happens to the NFA from states 1, 2 and 3 on a b. If the NFA is in state 1, then there is nowhere to go on a b; if the NFA is in state 2, then there is nowhere to go on a b; if the NFA is in state 3, then the NFA can go to 2 or 3 on b. Hence, if the NFA is in states 1, 2 and 3, the NFA on b can end in states 2 and 3. Thus, in the DFA, draw an edge from state {1, 2, 3} to a new state {2, 3}, which is accepting since it contains 2 ∈ F :
5
{2, 3}
b
{1,2} a {1,2,3} b
∅
a
Now do the same for DFA states {2, 3} and ∅. If any new DFA states arise, then we need to determine the a and b transitions out of those states as well. We stop once every DFA state has an a-transition and a b-transition out of it. Accepting states in the DFA are any DFA states that contain at least one accepting NFA state. We eventually end up with the DFA below as before:
b
{2, 3} a
b
{1,2} a {1,2,3}
b a,b
∅
a
For the DFA state ∅, there are no versions of the NFA currently active, i.e., all “threads” have “crashed,” so the NFA cannot proceed and the input string will not be accepted. However, according to the definition of a DFA, each state must have edges leaving it corresponding to each symbol in the alphabet Σ. Thus, we add a loop from the DFA state ∅ back to itself labeled with Σ, which in our case is a, b.
4. Give regular expressions that generate each of the following languages. In all cases, the alphabet is Σ = {a, b}.
6
(a) (b) (c) (d)
(e) (f )
The language {w ∈ Σ∗ | |w| is odd}.
Answer: (a ∪ b)((a ∪ b)(a ∪ b))∗
The language {w ∈ Σ∗ | w has an odd number of a’s}.
Answer: b∗a(ab∗a ∪ b)∗
The language { w | w contains at least two a’s, or exactly two b’s }.
Answer: b∗ab∗a(a ∪ b)∗ ∪ a∗ba∗ba∗
The language { w ∈ Σ∗ | w ends in a double letter }. (A string contains a double letter if it contains aa or bb as a substring.)
Answer: (a ∪ b)∗(aa ∪ bb)
The language {w ∈ Σ∗ | w does not end in a double letter}.
Answer: ε ∪ a ∪ b ∪ (a∪b)∗(ab∪ba)
The language { w ∈ Σ∗ | w contains exactly one double letter }. For example, baaba has exactly one double letter, but baaaba has two double letters.
Answer: (ε ∪ b)(ab)∗aa(ba)∗(ε ∪ b) ∪ (ε ∪ a)(ba)∗bb(ab)∗(ε ∪ a)
5. Suppose we define a restricted version of the Java programming language in which
variable names must satisfy all of the following conditions:
A variable name can only use Roman letters (i.e., a, b, …, z, A, B, …, Z) or Arabic numerals (i.e., 0, 1, 2, . . . , 9); i.e., underscore and dollar sign are not allowed.
A variable name must start with a Roman letter: a,b, …,z,A,B, …,Z
The length of a variable name must be no greater than 8.
A variable name cannot be a keyword (e.g., if). The set of keywords is finite.
Let L be the set of all valid variable names in our restricted version of Java.
(a) Let L0 be the set of strings satisfying the first 3 conditions above; i.e., we do not
require the last condition. Give a regular expression for L0. Answer: To simplify the regular expression, we define
Σ1 = {a,b,…,z,A,B,…,Z} Σ2 = {0,1,2, . . . ,9}.
Then a regular expression for L0 is
Σ1 (Σ1 ∪Σ2 ∪ε)···(Σ1 ∪Σ2 ∪ε).
7 times
Note that by including the ε in each of the last parts, we can generate strings that have length strictly less than 8.
7
(b) Prove that L has a regular expression, where L is the set of strings satisfying all four conditions.
Answer: We proved in Homework 1, problem 4(b), that L is finite. Thus, L is regular, so it has a regular expression. Although the problem didn’t ask for it, we can write a regular expression for L by listing all of the strings in L and putting a ∪ in between each pair of consecutive strings. This works because L is finite.
(c) Give a DFA for the language L0 in part (a), where the alphabet Σ is the set of all printable characters on a computer keyboard (no control characters), except for parentheses to avoid confusion.
Answer: Define Σ1 and Σ2 as in part (a), and let Σ3 = Σ−(Σ1 ∪Σ2) be all of the other characters on a computer keyboard except for parentheses. Then a DFA for L0 is as follows:
1 Σ1
2 Σ1∪Σ2 Σ3
Σ2 ∪ Σ3
3 Σ1∪Σ2 4
••• 9
Σ3
0
Σ
Σ3
Σ
6. Define L to be the set of strings that represent numbers in a modified version of Java. The goal in this problem is to define a regular expression and an NFA for L. To precisely define L, let the set of digits be Σ1 = {0,1,2, …,9}, and define the set of signs to be Σ2 = {+,-}. Then L = L1 ∪L2 ∪L3, where
L1 is the set of all strings that are decimal integer numbers. Specifically, L1 consists of strings that start with an optional sign, followed by one or more digits. Examples of strings in L1 are “02”, “+9”, and “-241”.
L2 is the set of all strings that are floating-point numbers that are not in expo- nential notation. Specifically, L2 consists of strings that start with an optional sign, followed by zero or more digits, followed by a decimal point, and end with zero or more digits, where there must be at least one digit in the string. Examples of strings in L2 are “13.231”, “-28.” and “.124”. All strings in L2 have exactly one decimal point.
L3 is the set of all strings that are floating-point numbers in exponential notation. Specifically, L3 consists of strings that start with a string from L1 or L2, followed by “E” or “e”, and end with a string from L1. Examples of strings in L3 are “-80.1E-083”, “+8.E5” and “1e+31”.
Assume that there is no limit on the number of digits in a string in L. Also, we do not allow for the suffixes L, l, F, f, D, d, at the end of numbers to denote types (long integers, floats, and doubles). Define Σ as the alphabet of all printable characters on a computer keyboard (no control characters), except for parentheses to avoid confusion.
8
(a) Give a regular expression for L1. Also, give an NFA and a DFA for L1 over the alphabet Σ.
Answer: A regular expression for L1 is
R 1 = ( + ∪ – ∪ ε ) Σ 1 Σ ∗1
where Σ1 = {0,1,2, …,9} as previously defined. An NFA for L1 is Σ1
+,-,ε Σ1
q1 q2 q3
Define Σ3 = Σ−(Σ1 ∪Σ2) with Σ2 = {-,+}, as before. Then a DFA for L1 is
Σ1
Σ1
3
Σ1
Σ − Σ1
4Σ
1 Σ2 2
Σ − Σ1
Σ3
Notice that the DFA is more complicated than the NFA.
(b) Give a regular expression for L2. Also, give an NFA for L2 over the alphabet Σ.
Answer: A regular expression for L2 is R2=(+∪-∪ε)(Σ1Σ∗1.Σ∗1 ∪.Σ1Σ∗1)
Note that the regular expression ( + ∪ – ∪ ε ) Σ∗1 . Σ∗1 is not correct since it can generate the strings “.”, “+.” and “-.”, which are not valid floating-point numbers.
An NFA for L2 is
Σ1
r3
Σ1 •
+,-,ε
r1r2 r5
Σ1
•
r4
Σ1
9
(c) Give a regular expression for L3. Also, give an NFA for L3 over the alphabet Σ. Answer: A regular expression for L3 is
R3 =(R1 ∪R2)(E∪e)R1
where R1 and R2 are defined in the previous parts. An NFA for L3 is
Σ1
s3
Σ1 •
Σ1
Σ1
+,-,ε
s1 s2•s4 s5 s6 s7 s8
Σ1
(d) Give a regular expression for the language L. Also, give an NFA for L over the alphabet Σ.
Answer: Note that L = L1 ∪ L2 ∪ L3, so a regular expression for L is R4 = R1 ∪ R2 ∪ R3
We can construct an NFA for L by taking the union of the NFA’s for L1, L2 and L3, as follows:
E,e +,-,ε Σ1
Σ1
10
Σ1
r3
Σ1 •
ε
+,-,ε Σ1
q1 q2 q3
Σ1
r
Σ1
q0 ε r +,-,ε r 125
ε
•
r4 Σ1
s3
Σ1 •
Σ1
Σ1
Σ1
+,-,ε
s1 s2•s4 s5 s6 s7 s8
Σ1
E,e +,-,ε Σ1
Σ1
A simpler NFA for L is to take the NFA for L3 and make s3 and s5 also accepting states in addition to s8.
11