Description
1. (35 points) For each one of the following languages give a proof that it is or is not regular.
(a)
{0
m1
n
|m ≥ 5 and n ≥ 0}.
(b)
{0
m1
n
|m ≥ n
2
}.
(c) The set of strings in {0, 1}
∗ which are not of the form ww for some w ∈ {0, 1}
∗
.
(d) Over the alphabet Σ = {0, 1}:
L = {x|x contains the same number of 01’s and 10’s as substrings}
(e) Over the alphabet Σ = {0, 1, 2}:
L = {x|x contains the same number of 01’s and 10’s as substrings}
(f) The first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of
the previous two: 0, 1, 1, 2, 3, 5, 8, 13, . . .. Now the language in question is
{0
n
|n is a Fibonacci number}.
1
(g) The set of strings in {0, 1}
∗ which are not palindromes:
{w ∈ {0, 1}
∗
| w 6= w
R}.
2. (a) (3 points) Find a left-most derivation for aaabbabbba in the following context-free grammar:
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
(b) (2 points) Draw the corresponding parse-tree of your left-most derivation.
3. (10 points) Show that the language of the grammar S → 0S1 | 1S0 | SS | ε is
{w ∈ {0, 1}
∗
| w contains the same number of zeros and ones}.
4. (20 Points) Construct a context free grammar for the set of all words w over the alphabet {0, 1}
such that each prefix1 of w has at least as many 0’s as 1’s. You have to prove that (i) every such
word can be generated with your grammar, and (ii) every word generated by your grammar has
the desired property.
5. (20 points) For each one of the following languages construct a context-free grammar that generates that language:
(a)
{0, 1}
∗
.
(b)
{0
m1
n
| m ≥ n and m − n is even}.
(c) The complement of {0
n1
n
| n ≥ 0} over the alphabet {0, 1}.
(d) The set of strings in {0, 1}
∗ which are not palindromes:
{w ∈ {0, 1}
∗
| w 6= w
R}.
6. (10 Points) Use the equivalence of context-free grammars and push-down automata to show that
if A and B are regular languages, then {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free.
1A prefix is a substring that starts from the beginning of the word.
2