Description
five. Prove that the following language over alphabet Σ= { 0, 1 } is not finite state using the
pumping lemma:
{ 0i
1
j
0
k
| i, j, k ≥ 0 and k = | i – j | }
“| i – j |” denotes the absolute value of (i – j)
1: Let alphabet ∑ = { a, b, c } . Consider the following languages over ∑ such that:
Lf
is a finite language, i.e. a set consisting of a finite number of strings
Lfs is a finite state language
L= = { xcy | x, y { a, b }*
and |x| = |y| } (as discussed in class, this is not a finite
state language)
Lnfs is not finite state language
Answer each question below about the given combinations of languages.
The possible answers are “always”, “sometimes”, or “never”.
Explain your answer by providing a brief justification, example, or counterexample, as
appropriate. Note that if your answer is “sometimes”, then to justify your answer you
need to provide two different examples: one where the combination is a finite state
language and one where the combination is not a finite state language. Briefly explain
why the language is or isn’t finite state, but you do not need to prove it.
a. Is Lf Lnfs a finite state language?
b. Is Lfs L= a finite state language?
c. Is Lf Lnfs a finite state language?
2: Let Σ = { 0, 1 }. Convert the following Regular Expression to an NFA via the compositional
construction in the proof of Sipser Lemma 1.55:
( 0* + 1* )*
3: Let ∑ = { a, b }. Prove that the following is finite state:
L3 = { w | for some string, x Σ
*
of length 3, w contains a substring x,
and w also contains a non-overlapping substring xR
}
Here, “non-overlapping” means that in string w, the occurrence of x and the occurrence of
x
R
do not overlap each other.
2
4: Let Σ= { a, b }, and let G = (V, Σ, R, S) be the context free grammar where:
V = { S, A, B }, and
R = S -> A | B | ε
A -> aC | Ca
C -> bS | Sb
B -> bD | Db
D -> aS | Sa
(a) Show a derivation tree in G of the string “aabb”.
(b) Show the left-most derivation of the string “aabb” corresponding to your tree in
part (a).
(c) Show a different derivation tree in G of the string “aabb”.
(d) Show the left-most derivation of the string “aabb” corresponding to your tree in
part (c).
5: Give a CFG for the following language over Σ= { a, b, c }:
L5 = { ai
b
j
c
k
| i, j, k ≥ 0, and j = i + k }
eof
