Math Problems Vault

Example 3.36

Consider the context-free grammar $G=(\left\{ S\right\} , \left\{ a, b\right\} , R, S)$ , with the rules

S \longrightarrow a S \mid a S b S \mid \varepsilon .

Construct a PDA $M$ such that $L(M)=L(G)$ .

?

Example 3.38

Construct a context-free grammar $G$ such that $L(G)= L(M)$ , where $M$ is the PDA of Example 3.29.

?

Example 3.39

Show that if $A$ is a regular language and $B$ is a context-free language, then $A \cap B$ is a context-free language.

?

Example 3.40

Show that $L= \left\{ 0,1\right\}^{*}-\left\{ \left(0^{m} 1^{m}\right)^{n} \mid m, n \geq 1\right\}$ is a contextfree language.

?

Example 3.41

Show that if $L_{1}$ is a context-free language and $L_{2}$ is a regular language, then the quotient $L_{1} / L_{2}$ is a context-free language.

?

Example 3.42

Show that if $L$ is regular, then

\widetilde{L}=\left\{ x z \mid (\exists y)[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in L]\right\}

is context-free.

?

Problem 3.5.1

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

For each of the following context-free grammars $G$ , following the procedure of Theorem 3.35 to construct a PDA that accepts the language $L(G)$ :

?

(a)

$S \rightarrow \varepsilon \mid a S b S \mid b S a S$ .

(b)

$S \longrightarrow \varepsilon \mid S S \mid a S b$ .

(c)

The grammar of Solution 2 to Example 3.6.

(d)

The unambiguous grammar of Example 3.24(b).

Problem 3.5.2

(a)(b)

For each of the following PDA's $M$ , following the procedure of Theorem 3.37 to construct a context-free grammar that generates the language $L(M)$ :

?

(a)

The PDA of Example 3.30.

(b)

The PDA of Figure 3.14(a) (for language $\left\{ a^{i} b^{j} \mid 2 i=3 j\right\}$ ).

Problem 3.5.3

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

Construct pushdown automata to accept the following languages:

?

(a)

$\left\{ 0^{n} 1^{m} \mid m \neq n, m \neq 2 n, m \neq 3 n\right\}$ .

(b)

$\left\{ a^{i} b^{j} c^{k} \mid i \neq j\text{ or }j \neq k\text{ or }i \neq k\right\}$ .

(c)

$\left\{ 0,1\right\}^{*}-\left\{ \left(0^{n} 1\right)^{n} \mid n \geq 1\right\}$ .

(d)

$\left\{ 0,1\right\}^{*}-\left\{ b_{i} \# b_{i+1} \mid b_{i}\text{ is the binary representation of }i, i \geq 1\right\}$ .

Problem 3.5.4

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

Show that if $L$ is a regular language, then each of the following languages is context-free:

?

(a)

$\left\{ x \in L \mid x=x^{R}\right\}$ .

(b)

$\left\{ w y \mid (\exists x, z)\left[\left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right]\right\}$ .

(c)

$\left\{ y x \mid (\exists w, z)\left[\left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right]\right\}$ .

(d)

$\left\{ x z \mid \left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right\}$ .

Problem 3.5.5

Show that $L_{1} \backslash L_{2}$ is a context-free language, if $L_{1}$ is context-free and $L_{2}$ is regular.

?

Problem 3.5.6

(a)(b)(c)

A two-stack pushdown automaton (2-stack PDA) is a PDA with two pushdown stacks. At each move, $M$ can read, in addition to an input symbol, the top symbols of both stacks, and to write symbols to both stacks. Formally, a 2 -stack PDA is a 6 -tuple $M=(Q, \Sigma , \Gamma , \delta , s, F)$ , where $Q, \Sigma , \Gamma , s, F$ are the same as those of a PDA, and $\delta$ is a transition function

\delta : Q \times (\Sigma \cup \left\{ \varepsilon \right\} ) \times (\Gamma \cup \left\{ \varepsilon \right\} )^{2} \rightarrow 2^{Q \times (\Gamma \cup \left\{ \varepsilon \right\} )^{2}}

Let $a \in \Sigma \cup \left\{ \varepsilon \right\}$ , and $u_{1}, u_{2}, v_{1}, v_{2} \in \Gamma \cup \left\{ \varepsilon \right\}$ . Then, an instruction $\left(p, v_{1}, v_{2}\right) \in \delta \left(q, a, u_{1}, u_{2}\right)$ , indicates that the PDA $M$ reads the input $a$ , the top symbol $u_{1}$ of stack 1, the top symbol $u_{2}$ of stack 2, and then it moves to state $p$ , repaces $u_{1}$ by $v_{1}$ and replaces $u_{2}$ by $v_{2}$ .

?

(a)

Define formally the notion of configurations and successor configurations of a 2 -stack PDA.

(b)

Construct a 2-stack PDA to accept the language $\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$ .

(c)

Construct a 2 -stack PDA to accept the language $\left\{ a^{n} b^{m} c^{n} d^{m} \mid n \geq m\right\}$ .

Problem 3.5.7

A pushdown automaton $M$ is called a linear-bounded PDA if there is a constant $c>0$ such that the size of the stack of $M$ , during its computation on any input $x$ , is bounded by $c\left|x\right|$ . Show that the class of languages accepted by linear-bounded PDA's is exactly the class of context-free languages.

?