Context-Free Languages

Recall the CFG $G_{4}$ that we gave in Example 2.4. For convenience, let's rename its variables with single letters as follows.

Give parse trees and derivations for each string.

ᴬ Answer each part for the following context-free grammar $G$.

Give context-free grammars that generate the following languages. In all parts, the alphabet $\Sigma$ is 0,1.

Give informal descriptions and state diagrams of pushdown automata for the languages in Exercise 2.4. In all parts, the alphabet $\Sigma$ is 0,1.

Give context-free grammars generating the following languages.

ᴬ Give informal English descriptions of PDAs for the languages in Exercise 2.6.

ᴬ Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_{2}$ on page 103. Describe in English the two different meanings of this sentence.

Give a context-free grammar that generates the language

Is your grammar ambiguous? Why or why not?

Give an informal description of a pushdown automaton that recognizes the language $A$ in Exercise 2.9.

Convert the CFG $G_{4}$ given in Exercise 2.1 to an equivalent PDA, using the procedure given in Theorem 2.20.

Convert the CFG $G$ given in Exercise 2.3 to an equivalent PDA, using the procedure given in Theorem 2.20.

Let $G=(V, \Sigma , R, S)$ be the following grammar. $V=\left\{ S, T, U\right\} ; \Sigma =\left\{ 0, \# \right\}$; and $R$ is the set of rules:

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.

Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let $A$ be a CFL that is generated by the CFG $G=(V, \Sigma , R, S)$. Add the new rule $S \rightarrow S S$ and call the resulting grammar $G^{\prime }$. This grammar is supposed to generate $A^{*}$.

Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

Use the results of Exercise 2.16 to give another proof that every regular language is context free, by showing how to convert a regular expression directly to an equivalent context-free grammar.

ᴬ

• Let CFG $G$ be the following grammar.

Give a simple description of $L(G)$ in English. Use that description to give a CFG for $\overline{L(G)}$, the complement of $L(G)$.

Let $A / B=\left\{ w \mid w x \in A\text{ for some }x \in B\right\}$. Show that if $A$ is context free and $B$ is regular, then $A / B$ is context free.

• Let $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. Give a CFG generating the language of strings with twice as many a's as b's. Prove that your grammar is correct.

• Let $C=\left\{ x \# y \mid x, y \in \left\{ 0,1\right\}^{*} \text{ and } x \neq y\right\}$. Show that $C$ is a context-free language.

• Let $D=\left\{ x y \mid x, y \in \left\{ 0,1\right\}^{*} \text{ and } \left|x\right|=\left|y\right| \text{ but } x \neq y\right\}$. Show that $D$ is a context-free language.

• Let $E=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mid i \neq j \text{ and } 2 i \neq j\right\}$. Show that $E$ is a context-free language.

For any language $A$, let $\operatorname {SUFFIX}(A)=\left\{ v \mid u v \in A\text{ for some string }u\right\}$. Show that the class of context-free languages is closed under the SUFFIX operation.

Show that if $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n \geq 1$, exactly $2 n-1$ steps are required for any derivation of $w$.

• Let $G=(V, \Sigma , R,\langle$ STMT $\rangle )$ be the following grammar.

$G$ is a natural-looking grammar for a fragment of a programming language, but $G$ is ambiguous.

• Give unambiguous CFGs for the following languages.

• Show that the language $A$ in Exercise 2.9 is inherently ambiguous.

Use the pumping lemma to show that the following languages are not context free.

Let $B$ be the language of all palindromes over 0,1 containing equal numbers of 0s and 1s. Show that $B$ is not context free.

Let $\Sigma =\left\{ 1,2,3,4\right\}$ and $C=\left\{ w \in \Sigma^{*} \mid \text{ in } w\text{, the number of 1s equals the number of 2s, and the number of 3s equals the number of 4s}\right\}$. Show that $C$ is not context free.

• Show that $F=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mid i=k j \text{ for some positive integer } k\right\}$ is not context free.

Consider the language $B=L(G)$, where $G$ is the grammar given in Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34, states the existence of a pumping length $p$ for $B$. What is the minimum value of $p$ that works in the pumping lemma? Justify your answer.

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 $v$ and $y$ must be nonempty when the string $s$ is broken up. If $A$ is a context-free language, then there is a number $k$ where, if $s$ is any string in $A$ of length at least $k$, then $s$ may be divided into five pieces, $s=u v x y z$, satisfying the conditions:

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

Problem 1.41: For languages $A$ and $B$, the perfect shuffle of $A$ and $B$ is the language

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.

Problem 1.42: For languages $A$ and $B$, the shuffle of $A$ and $B$ is the language

• 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 $\operatorname {NOPREFIX}(A)$ and $\operatorname {NOEXTEND}(A)$ in Problem 1.40.

• Let $Y=\left\{ w \mid w=t_{1} \# t_{2} \# \cdots \# t_{k} \text{ for } k \geq 0, \text{ each } t_{i} \in 1^{*}, \text{ and } t_{i} \neq t_{j} \text{ whenever } i \neq j\right\}$. Here $\Sigma =\left\{ 1, \# \right\}$. Prove that $Y$ is not context free.

For strings $w$ and $t$, write $w \stackrel{\circ }{=} t$ if the symbols of $w$ are a permutation of the symbols of $t$. In other words, $w \stackrel{\circ }{=} t$ if $t$ and $w$ have the same symbols in the same quantities, but possibly in a different order. For any string $w$, define $\operatorname {SCRAMBLE}(w)=\left\{ t \mid t \stackrel{\circ }{=} w\right\}$. For any language $A$, let $\operatorname {SCRAMBLE}(A)=\left\{ t \mid t \in \operatorname {SCRAMBLE}(w)\text{ for some }w \in A\right\}$.

If $A$ and $B$ are languages, define $A \diamond B=\left\{ x y \mid x \in A\text{ and }y \in B\text{ and }\left|x\right|=\left|y\right|\right\}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.

• Let $A=\left\{ w t w^{\mathcal{R}} \mid w, t \in \left\{ 0,1\right\}^{*} \text{ and } \left|w\right|=\left|t\right|\right\}$. Prove that $A$ is not a CFL.

Consider the following CFG $G$ :

Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H)=L(G)$ and sketch a proof that $H$ is unambiguous.

Let $\Sigma =\left\{ 0,1\right\}$ and let $B$ be the collection of strings that contain at least one 1 in their second half. In other words, $B=\left\{ u v \mid u \in \Sigma^{*}, v \in \Sigma^{*} 1 \Sigma^{*} \text{ and } \left|u\right| \geq \left|v\right|\right\}$.

Let $\Sigma =\left\{ 0,1\right\}$. Let $C_{1}$ be the language of all strings that contain a 1 in their middle third. Let $C_{2}$ be the language of all strings that contain two 1s in their middle third. So $C_{1}=\left\{ x y z \mid x, z \in \Sigma^{*}, y \in \Sigma^{*} 1 \Sigma^{*}, \text{ where } \left|x\right|=\left|z\right| \geq \left|y\right|\right\}$ and $C_{2}=\left\{ x y z \mid x, z \in \Sigma^{*}, y \in \Sigma^{*} 1 \Sigma^{*} 1 \Sigma^{*}, \text{ where } \left|x\right|=\left|z\right| \geq \left|y\right|\right\}$.

• We defined the rotational closure of language $A$ to be $\operatorname {RC}(A)=\left\{ y x \mid x y \in A\right\}$. Show that the class of CFLs is closed under rotational closure.

• We defined the CUT of language $A$ to be $\operatorname {CUT}(A)=\left\{ y x z \mid x y z \in A\right\}$. Show that the class of CFLs is not closed under CUT.

Show that every DCFG is an unambiguous CFG.

ᴬ Show that every DCFG generates a prefix-free language.

• Show that the class of DCFLs is not closed under the following operations:

Let $G$ be the following grammar:

Let $G_{1}$ be the following grammar that we introduced in Example 2.45. Use the $D K$-test to show that $G_{1}$ is not a DCFG.

• Let $A=L\left(G_{1}\right)$ where $G_{1}$ is defined in Problem 2.55. Show that $A$ is not a DCFL. (Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ so that its input alphabet is $\left\{ \mathrm{a}, \mathrm{b}, \mathrm{c}\right\}$. When it first enters an accept state, it pretends that c's are b's in the input from that point on. What language would the modified $P$ accept?)

Problem 2.55: $G_{1}$ is the grammar

• Let $B=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0 \text{ and } i=j \text{ or } i=k\right\}$. Prove that $B$ is not a DCFL.

• Let $C=\left\{ w w^{\mathcal{R}} \mid w \in \left\{ 0,1\right\}^{*}\right\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its stack below $x$, no matter what input string $P$ reads from that point on. In that case, the contents of $P$ 's stack at that point cannot affect its subsequent behavior, so $P$ 's subsequent behavior can depend only on $q$ and $x$.)

• If we disallow $\varepsilon$-rules in CFGs, we can simplify the $D K$-test. In the simplified test, we only need to check that each of $D K$ 's accept states has a single rule. Prove that a CFG without $\boldsymbol {\varepsilon }$-rules passes the simplified $D K$-test iff it is a DCFG.