CSE 468, Fall 2000, Final: Solutions of selected exercises

Exercise 1

  1. By structural induction on the way a string x in L(G) can be generated:

  2. L does not coincide with L(G). In fact, baa is in L but not in L(G).

  3. 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

  1. L1 is context free. A grammar generating L1 is the following:
       S -> T | UV
       T -> aTc | B
       B -> bB | lambda
       U -> aUb | lambda
       V -> bVc | lambda

  2. L2 is not context free. It's possible to prove it by using the pumping lemma. (Proof omitted.)

  3. L3 is context free. A grammar generating L3 is the following:
       S -> UV
       U -> aUb | lambda
       V -> cVd | lambda

Exercise 5

L is recursively enumerable, but not decidable. In fact:
  1. 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.
  2. L is not recursive because the property "M accepts 00" is not trivial, hence by the theorem of Rice L cannot be recursive.