Description
Problem 1 (20 points)
Let Σ = {a, b, c}. Define a Context-free Language (CFL)
L = { a
i
b
j
c
i
| i, j ≥ 0 }.
(10 points) Find a Context-free Grammar (CFG) to describe L .
(10 points) Construct a PDA that recognizes L . Draw the state
diagram like Figure 2.15 in the textbook.
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
(10 points) Prove that if L is a context-free language and L 0
is a
regular language, then L ∩ L 0
is context-free too.
(10 points) Let Σ = {a, b, c} and
L = { w ∈ Σ
∗
| w contains equal numbers of a’s, b’s, and c’s }.
Use the first part to prove that L is not a context-free language.
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
A Right Linear Grammar (RLG) is a context-free grammar such
that in each production rule, at most one variable can appear in the
right-hand side and such an occurrence can only take place at the
right end. For example, the following is an RLG.
S → abS | abS |
Prove that RLGs recognize exactly the class of regular languages.
Your proof should consists of two parts: (1) any regular language
can be described by an RLG (10 points), and (2) any language
described by an RLG is regular (10 points).
Hint: Correspondence between the variables in an RLG and the
states of a DFA.
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
Use the pumping lemma to show that the following lanugage is not
context-free.
{ a
i
b
j
c
k
| i, j, k ≥ 0 and i > j and j > k }
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
Let G = h{S}, {a, b}, R, Si be a context-free grammar where R
consists of the following production rules:
S → aS | aSbS |
(5 points) Prove that G is ambiguous.
(15 points) Give an unambiguous grammar that generates the same
language as G does.
Hint: Use precedence as in Example 2.4 in the textbook.
6 / 6
CS 331: Theory of Computing
