CSE 468, Fall 2000, Final: Solutions of selected exercises
Exercise 1
By structural induction on the way a string x in L(G) can be generated:
Base
Case x = lambda: n_{a}(x) = n_{b}(x) = 0
Case x = aba: n_{a}(x) = 2 and n_{b}(x) = 1
Inductive case. Let x = aybza, with y, z in L(G).
Then n_{a}(x) = n_{a}(y) + n_{a}(z) + 2, while
n_{b}(x) = n_{b}(y) + n_{b}(z) + 1. By
inductive hypothesis, n_{a}(y) = 2 n_{b}(y), and
n_{a}(z) = 2 n_{b}(z). Hence n_{a}(x) = 2 n_{b}(x).
L does not coincide with L(G). In fact, baa is in L but not in L(G).
The grammar is ambiguous, because the string aba can be generated in two different
ways, namely recursively, by using the second production, or directly, by using the
third production.
To eliminate the ambiguity it is sufficient to eliminate the third
production. Hence an equivalent unambiguous grammar is the following:
S -> lambda | aSbSa
Exercise 2
L_{1} is context free. A grammar generating L_{1} is the following:
S -> T | UV
T -> aTc | B
B -> bB | lambda
U -> aUb | lambda
V -> bVc | lambda
L_{2} is not context free. It's possible to prove it by using
the pumping lemma. (Proof omitted.)
L_{3} is context free. A grammar generating L_{3} is the following:
S -> UV
U -> aUb | lambda
V -> cVd | lambda
Exercise 5
L is recursively enumerable, but not decidable. In fact:
L can be recognized by a TM M' such that, given input x, if x = e(M) for
some M then M' emulates the TM M on input 00. If x is not the encoding of
any TM then M' crashes.
L is not recursive because the property "M accepts 00" is not
trivial, hence by the theorem of Rice L cannot be recursive.