Math Problems Vault

Problem 2.1

(a)(b)(c)(d)

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

\begin{aligned} & E \rightarrow E+T \mid T \\ & T \rightarrow T \times F \mid F \\ & F \rightarrow (E) \mid \mathrm{a} \end{aligned}

Give parse trees and derivations for each string.

?

(a)

a

(b)

$\mathrm{a}+\mathrm{a}$

(c)

$a+a+a$

(d)

((a))

Problem 2.2

(a)(b)

?

(a)

Use the languages $A=\left\{ \mathrm{a}^{m} \mathrm{~ b}^{n} \mathrm{c}^{n} \mid m, n \geq 0\right\}$ and $B=\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mathrm{c}^{m} \mid m, n \geq 0\right\}$ together with Example 2.36 to show that the class of context-free languages is not closed under intersection.

(b)

Use part (a) and DeMorgan's law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.

Problem 2.3

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

\begin{aligned} R & \rightarrow X R X \mid S \\ S & \rightarrow \mathrm{a} T \mathrm{~ b} \mid \mathrm{b} T \mathrm{a} \\ T & \rightarrow X T X \mid X \mid \varepsilon \\ X & \rightarrow \mathrm{a} \mid \mathrm{b} \end{aligned}

?

(a)

What are the variables of $G$ ?

(b)

What are the terminals of $G$ ?

(c)

Which is the start variable of $G$ ?

(d)

Give three strings in $L(G)$ .

(e)

Give three strings not in $L(G)$ .

(f)

True or False: $T \Rightarrow \mathrm{aba}$ .

(g)

True or False: $T \stackrel{*}{\Rightarrow }$ aba.

(h)

True or False: $T \Rightarrow T$ .

(i)

True or False: $T \stackrel{*}{\Rightarrow } T$ .

(j)

True or False: $X X X \stackrel{*}{\Rightarrow }$ aba.

(k)

True or False: $X \stackrel{*}{\Rightarrow }$ aba.

(l)

True or False: $T \xrightarrow {*} X X$ .

(m)

True or False: $T \stackrel{*}{\Rightarrow } X X X$ .

(n)

True or False: $S \stackrel{*}{\Rightarrow } \varepsilon$ .

(o)

Give a description in English of $L(G)$ .

Problem 2.4

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

?

(a)

ᴬ $\left\{ w \mid w\text{ contains at least three 1 s }\right\}$

(b)

$\left\{ w \mid w\text{ starts and ends with the same symbol}\right\}$

(c)

$\left\{ w \mid \text{the length of } w \text{ is odd}\right\}$

(d)

ᴬ $\left\{ w \mid \text{ the length of }w\text{ is odd and its middle symbol is a 0}\right\}$

(e)

$\left\{ w \mid w=w^{\mathcal{R}}, \text{ that is, } w \text{ is a palindrome}\right\}$

(f)

The empty set

Problem 2.5

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.

?

(a)

$\left\{ w \mid w\text{ contains at least three 1 s }\right\}$

(b)

$\left\{ w \mid w\text{ starts and ends with the same symbol}\right\}$

(c)

$\left\{ w \mid \text{the length of } w \text{ is odd}\right\}$

(d)

$\left\{ w \mid \text{ the length of }w\text{ is odd and its middle symbol is a 0}\right\}$

(e)

$\left\{ w \mid w=w^{\mathcal{R}}, \text{ that is, } w \text{ is a palindrome}\right\}$

(f)

The empty set

Problem 2.6

(a)(b)(c)(d)

Give context-free grammars generating the following languages.

?

(a)

ᴬ The set of strings over the alphabet $\left\{ \mathbf{a}, \mathbf{b}\right\}$ with more a's than b's

(b)

The complement of the language $\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mid n \geq 0\right\}$

(c)

ᴬ $\left\{ w \# x \mid w^{\mathcal{R}} \text{ is a substring of } x \text{ for } w, x \in \left\{ 0,1\right\}^{*}\right\}$

(d)

$\left\{ x_{1} \# x_{2} \# \cdots \# x_{k} \mid k \geq 1, \text{ each } x_{i} \in \left\{ \mathrm{a}, \mathrm{b}\right\}^{*}, \text{ and for some } i \text{ and } j, x_{i}=x_{j}^{\mathcal{R}}\right\}$

Problem 2.7

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

?

Problem 2.8

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

?

Problem 2.9

Give a context-free grammar that generates the language

A=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i=j \text{ or } j=k \text{ where } i, j, k \geq 0\right\} .

Is your grammar ambiguous? Why or why not?

?

Problem 2.10

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

?

Problem 2.11

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

?

Problem 2.12

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

?

Problem 2.13

(a)(b)

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:

\begin{aligned} S & \rightarrow T T \mid U \\ T & \rightarrow 0 T \mid T 0 \mid \# \\ U & \rightarrow 0 U 00 \mid \# \end{aligned}

?

(a)

Describe $L(G)$ in English.

(b)

Prove that $L(G)$ is not regular.

Problem 2.14

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

\begin{aligned} & A \rightarrow B A B \mid B \mid \varepsilon \\ & B \rightarrow 00 \mid \varepsilon \end{aligned}

?

Problem 2.15

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^{*}$ .

?

Problem 2.16

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

?

Problem 2.17

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.

?