4.5  ADDITIONAL EXERCISES

  1. Modify the PDA in 4.2.1.4 to accept {0n 1n : n ≥ 1} by ES.
  2. Modify the PDA in 4.2.1.4 to accept {0n 1n : n ≥ 3} by ES.
  3. Build a PDA over an input alphabet ∑ that accepts strings by ES, and (provably) accepts {xxR : x images ∑*}.
  4. Build a PDA for the language {0n15n : n ≥ 0}. You are free to choose the mode of acceptance.
  5. Repeat the above task, but now do it in this way: First get a CFG for the language, and then construct a PDA for the language that accepts by empty stack (cf. 4.3.0.5).
  6. Give a CFG G over ∑ = {0, 1} such that L(G) = {xxR : x images ∑*}.
  7. Give a CFG G over ∑ = {(, )} such that L(G) is the full set of balanced brackets—that is, not only those of the form ((())) but also those like ((())) (()).
  8. Provide a complete proof for the claims in Example 4.3.0.7.
  9. By induction on regular expression length prove: “For every α, there is a CFG, G, such that L(G) = L(α)”.
  10. Prove that CFL are closed under union, that is, if L and L′ are CFL, then so is LL′.
  11. Prove that CFL are closed under concatenation, that is, if L and L′ are CFL, then so is LL′.
  12. Prove that CFL are closed under reversal, that is, if L is a CFL, then so is LR.
  13. Prove that CFL are not closed under complement. That is, if L is a CFL over ∑, then it is not necessarily the case that , that is, ∑* − L is a CFL. ...

Get Theory of Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.