Theory of Computation

4.5  ADDITIONAL EXERCISES

1. Modify the PDA in 4.2.1.4 to accept {0ⁿ 1ⁿ : n ≥ 1} by ES.
2. Modify the PDA in 4.2.1.4 to accept {0ⁿ 1ⁿ : n ≥ 3} by ES.
3. Build a PDA over an input alphabet ∑ that accepts strings by ES, and (provably) accepts {xx^R : x ∑*}.
4. Build a PDA for the language {0ⁿ1⁵ⁿ : 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) = {xx^R : x ∑*}.
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 L ∪ L′.
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 L^R.
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. ...