Description
5. Consider the following two languages over Σ = { a, b, c }.
Lfive = { xby | x, y ∈ { a, c }*
and the number of a’s in x = the number of a‘s in y }
LNFS = { an
ban | n ≥ 0 }
As discussed in class, languages like LNFS are not finite state. Prove that Lfive is not finite
state using closure properties of finite state languages and the fact that LNFS is not finite state.
zero. Show a DFA over the alphabet { a, b } for the following language via the construction in the
proof of Theorem 1.25 (that Finite State Languages are closed under union) and the
footnote 3 on p. 46 (that Finite State Languages are closed under intersection). First
construct two DFAs such that the language below is the intersection of the languages of
the two DFAs, as in Sipser exercise 1.4:
{ w ∈ Σ
*
| w starts with symbol b and contains at most one symbol a }
one. Consider the language over alphabet Σ = { a, b, c }:
Lone = { w ∈ Σ+ | w begins and ends with c }
a. Show an NFA for (Lone)* by defining a DFA for Lone and then using the Kleene star
construction in the proof of Theorem 1.49.
b. Is (Lone)* the same as Lone ? Very briefly explain your answer.
two. Consider the following language over Σ = { 0, 1 }:
Ltwo = { w ∈ Σ+ | if w begins with a 1, |w| is odd; and if w begins with a 0, |w| is even }
a: Show an NFA for the language Ltwo • Ltwo , by defining a DFA for Ltwo and then using the
concatenation construction in the proof of Theorem 1.47.
b: Does Ltwo • Ltwo = Ltwo ? Very briefly explain your answer.
three: Let Σ= { 0, 1 }. Give a regular expression for the language:
{ w ∈ Σ* | w contains at least two 0s and at most one 1 }
four. Refer to Figure 1.61, Sipser page 70, with the internal states named as shown here:
a: Verify that ababaaba is accepted by the GNFA.
Show a sequence of states qstart, q1, … qk-1, qaccept , and the corresponding sequence of
words w1…wk in the accepting computation.
b: Verify or refute the following claim and briefly justify your answer:
Every string accepted by the GNFA that contains more then one b has an
odd number of a’s.
five. Prove that the following language over alphabet Σ= { 0, 1 } is not finite state using the
pumping lemma:
{ 0
i
1
j
0
k | i, j, k ≥ 0 and k = | i – j | }
“| i – j |” denotes the absolute value of (i – j)
eof
