### 4.5 ADDITIONAL EXERCISES

- Modify the PDA in 4.2.1.4 to accept {0
^{n}1^{n}:*n*≥ 1} by ES. - Modify the PDA in 4.2.1.4 to accept {0
^{n}1^{n}:*n*≥ 3} by ES. - Build a PDA over an input alphabet ∑ that accepts strings by ES, and (provably) accepts {
*xx*:^{R}*x*∑*}. - Build a PDA for the language {0
^{n}1^{5n}:*n*≥ 0}. You are free to choose the mode of acceptance. - 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).
- Give a CFG
*G*over ∑ = {0, 1} such that*L*(*G*) = {*xx*:^{R}*x*∑*}. - 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 ((())) (()). - Provide a complete proof for the claims in Example 4.3.0.7.
- By induction on regular expression length prove: “For every α, there is a CFG,
*G*, such that*L*(*G*) =*L*(α)”. - Prove that CFL are closed under union, that is, if
*L*and*L*′ are CFL, then so is*L*∪*L*′. - Prove that CFL are closed under concatenation, that is, if
*L*and*L*′ are CFL, then so is*LL*′. - Prove that CFL are closed under reversal, that is, if
*L*is a CFL, then so is*L*.^{R} - 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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.