91影视

Let G be a CFG in Chomsky normal form that contains b variables.

Show that if G generates some string with a derivation having at least $2^b$

steps, L(G)is infinite.

Give an example of a language that is not context free but that acts like a CFL in the pumping lemma. Prove that your example works. (See the analogous example for regular languages in Problem 1.54.)

Prove the following stronger form of the pumping lemma, wherein both pieces $\mathbf{v}\mathbf{}\mathbf{and}\mathbf{}\mathbf{y}$ must be nonempty when the string$\mathbf{S}$ is broken up.

If $\mathbf{A}$is a context-free language, then there is a number k where, if s is any string in$\mathbf{A}$ of length at least$\mathbf{k}$ , then s may be divided into five pieces,role="math" localid="1659706026393" $\mathbf{s}\mathbf{=}\mathbf{uvxyz}$ , satisfying the conditions:

role="math" localid="1659706054658" $\begin{array}{l}\mathbf{a}\mathbf{.}\mathbf{}\mathbf{for}\mathbf{}\mathbf{each}\mathbf{}\mathbf{i}\mathbf{鈮�}\mathbf{0}\mathbf{,}{\mathbf{uv}}^{\mathbf{i}}{\mathbf{xy}}^{\mathbf{i}}\mathbf{z}\mathbf{鈭�}\mathbf{A}\mathbf{,}\\ \mathbf{b}\mathbf{.}\mathbf{v}\mathbf{鈮�}\mathbf{蔚}\mathbf{}\mathbf{and}\mathbf{}\mathbf{y}\mathbf{鈮�}\mathbf{蔚}\mathbf{,}\mathbf{and}\\ \mathbf{c}\mathbf{.}\mathbf{\left|}\mathbf{vxy}\mathbf{\right|}\mathbf{鈮�}\mathbf{k}\mathbf{,}\end{array}$

Refer to Problem 1.41 for the definition of the perfect shuffle operation. Show that the class of context-free languages is not closed under perfect shuffle.

$\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{=}{\mathbf{a}}_{\mathbf{1}}{\mathbf{b}}_{\mathbf{1}}\mathbf{........}{\mathbf{a}}_{\mathbf{k}}{\mathbf{b}}_{\mathbf{k}}\mathbf{where}\mathbf{\text{鈥娾赌娾赌�}}{\mathbf{a}}_{\mathbf{1}}\mathbf{.......}{\mathbf{a}}_{\mathbf{k}}\mathbf{鈭�}\mathbf{A}\mathbf{\text{鈥娾赌娾赌�}}\mathbf{and}\mathbf{\text{鈥娾赌娾赌�}}{\mathbf{b}}_{\mathbf{1}}\mathbf{.......}{\mathbf{b}}_{\mathbf{k}}\mathbf{鈭�}\mathbf{B}\mathbf{,}\mathbf{each}\mathbf{\text{鈥娾赌�}}{\mathbf{a}}_{\mathbf{i}}{\mathbf{b}}_{\mathbf{i}}\mathbf{鈭�}\mathbf{鈭�}\mathbf{\right\}}\mathbf{.}$

Refer to Problem 1.42 for the definition of the shuffle operation. Show that the class of context-free languages is not closed under shuffle.

$\left\{w|w=a_1{b}_1........a_k{b}_k\mathrm{where}\text{鈥娾赌娾赌�}{a}_1.......a_k鈭�A\text{鈥娾赌娾赌�}\mathrm{and}\text{鈥娾赌娾赌�}{b}_1.......b_k鈭�B,\mathrm{each}\text{鈥娾赌�}{a}_i{b}_i鈭�{鈭�}^{*}\right\}\mathbf{.}$

Answer each part for the following context-free grammar G

$\begin{array}{l}\mathbf{R}\mathbf{鈫�}\mathbf{XRX}\mathbf{|}\mathbf{S}\\ \mathbf{S}\mathbf{鈫�}\mathbf{aTb}\mathbf{|}\mathbf{bTa}\\ \mathbf{T}\mathbf{鈫�}\mathbf{XTX}\mathbf{\left|}\mathbf{X}\mathbf{\right|}\mathbf{蔚}\\ \mathbf{X}\mathbf{鈫�}\mathbf{a}\mathbf{|}\mathbf{b}\end{array}$

1. What are the variables of $\mathbf{G}$?
2. What are the terminals of $\mathbf{G}$?
3. Which is the start variable of $\mathbf{G}$?
4. Give three strings in $\mathbf{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$.
5. Give three strings not in$\mathbf{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$ .
6. True or False: $\mathbf{T}\mathbf{鈬�}\mathbf{aba}$.
7. True or False: $\mathbf{T}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{aba}$.
8. True or False:$\mathbf{T}\mathbf{鈬�}\mathbf{T}$ .
9. True or False: $\mathbf{T}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{T}$.
10. True or False:$\mathbf{XXX}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{aba}$ .
11. True or False: $\mathbf{X}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{aba}$
12. True or False:role="math" localid="1660812124187" $\mathbf{T}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{XX}$.
13. True or False: $\mathbf{T}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{XXX}$.
14. True or False: $\mathbf{S}\stackrel{\mathbf{鈭�}}{\mathbf{鈬�}}\mathbf{蔚}$.
15. Give a description in English of $\mathbf{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$ .

Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C contains an infinite regular subset.

Read the definitions of NOPREFIX ( $\mathbf{A}$) and NOEXTEND ($\mathbf{A}$) in Problem .

a. Show that the class of CFLs is not closed under NOPREFIX.

b. Show that the class of CFLs is not closed under NOEXTEND.

Let

$\mathbf{y}\mathbf{=}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{=}{\mathbf{t}}_{\mathbf{1}}\mathbf{\#}{\mathbf{t}}_{\mathbf{2}}\mathbf{\#}\mathbf{.}\mathbf{......}\mathbf{\#}{\mathbf{t}}_{\mathbf{k}}\mathbf{\text{鈥�}}\mathbf{for}\mathbf{\text{鈥娾赌�}}\mathbf{k}\mathbf{鈮�}\mathbf{0}\mathbf{\text{鈥娾赌娾赌�}}\mathbf{each}\mathbf{\text{鈥娾赌�}}{\mathbf{t}}_{\mathbf{i}}\mathbf{鈭�}{\mathbf{1}}^{\mathbf{*}}\mathbf{,}\mathbf{\text{鈥娾赌�}}\mathbf{and}\mathbf{\text{鈥娾赌�}}{\mathbf{t}}_{\mathbf{i}}\mathbf{鈮�}{\mathbf{t}}_{\mathbf{j}}\mathbf{\text{鈥娾赌�}}\mathbf{whenever}\mathbf{\text{鈥娾赌�}}\mathbf{i}\mathbf{鈮�}\mathbf{j}\mathbf{\right\}}$.

Here$\mathbf{危}\mathbf{=}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{\#}\mathbf{\}}\mathbf{.}$ Prove that $\mathbf{Y}$ is not context free.

For string W and t , write if the symbols of W are a permutation of the symbols of t . In other word,$\mathit{w}\mathbf{鈮�}\mathit{t}$ if t and W have the same symbols in the same quantities, but possibly in a different order.

For any string W , defines $\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{t}\mathbf{|}\mathbf{t}\mathbf{鈮�}\mathbf{w}\mathbf{\right\}}$. For any language A, let .$\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{t}\mathbf{|}\mathbf{t}\mathbf{鈭�}\mathbf{S}\mathbf{C}\mathbf{R}\mathbf{A}\mathbf{M}\mathbf{B}\mathbf{L}\mathbf{E}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{\text{鈥塮辞谤鈥塻辞尘别鈥�}}\mathbf{w}\mathbf{鈭�}\mathbf{A}\mathbf{\right\}}$

1. Show that if$\mathbf{鈭�}\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}$ , then the $\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}$of a regular language is context free.
2. What happens in part (a) if$鈭�$ contains three or more symbols? Prove your answer.