Math Problems Vault

Example 3.28

Consider the PDA $M=(\left\{ q, p\right\} , \left\{ a, b, c\right\} , \left\{ a, b\right\} , \delta , q,\left\{ p\right\} )$ , where $\delta$ is defined as follows:

\begin{array}{ll} \delta (q, a, \varepsilon )=\left\{ (q, a)\right\} , & \delta (p, a, a)=\left\{ (p, \varepsilon )\right\} , \\ \delta (q, b, \varepsilon )=\left\{ (q, b)\right\} , & \delta (p, b, b)=\left\{ (p, \varepsilon )\right\} , \\ \delta (q, c, \varepsilon )=\left\{ (p, \varepsilon )\right\} . & \end{array}

Determine what $L(M)$ is.

?

Example 3.29

Construct a PDA accepting the language $\left\{ w w^{R} \mid w \in \left\{ a, b\right\}^{*}\right\}$ .

?

Example 3.30

Construct a PDA that accepts the language

\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0, i+k=j\right\} .

?

Example 3.31

Construct a PDA that accepts the language

L=\left\{ a^{i} b^{j} \mid 2 i \neq 3 j\right\} .

?

Example 3.32

Construct a PDA that accepts the language

L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid 2 \# _{a}(x) \neq 3 \# _{b}(x)\right\} .

?

Example 3.33

Construct a PDA M that accepts the following language:

\left\{ w \in \left\{ a, b\right\} ^{*} \mid \# _{a}(w) \leq \# _{b}(w) \leq 2 \# _{a}(w)\right\} .

?

Example 3.34

Construct a PDA $M$ that accepts the language

L=\left\{ w \in \left\{ a, b\right\} ^{*} \mid 3 \# _{a}(w) \leq 5 \# _{b}(w) \leq 4 \# _{a}(w)\right\} .

?

Problem 3.4.1

For each of the following languages $L$ , construct a PDA to accept $L$ . In addition, for each given string $x \in L$ , show an accepting computation path of your PDA on $x$ .

?

(a)

$\left\{ a^{n} b^{m} \mid m, n \geq 0, m \neq 3 n\right\} ; x=a^{2} b^{4}$ .

(b)

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq m \leq 3 n\right\} ; x=a^{2} b^{5}$ .

(c)

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq 3 m \leq 4 n-2\right\} ; x=a^{3} b^{3}$ .

(d)

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0, i+2 k=j\right\} ; x=a^{3} b^{7} c^{2}$ .

(e)

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0,2 i+3 k \leq 4 j\right\} ; x=a^{4} b^{4} c^{2}$ .

(f)

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0, i+k \leq j+l\right\} ; x=a^{2} b^{4} c^{5} d^{3}$ .

(g)

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0,2 i+3 k \leq 4 j+l\right\} ; x=a^{3} b^{4} c^{4} d^{5}$ .

(h)

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w)+5 \leq 3 \#_{b}(w)\right\} ; x=a b b a b b a$ .

(i)

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w) \leq 3 \#_{b}(w) \leq 4 \#_{a}(w)\right\} ; x=a b b a a a b$ .

(j)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w)\right\} ; x=a a c a b b b a a$ .

(k)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid 2 \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w) \leq 5 \#_{a}(w)\right\} ; x=$ acabcc.

Problem 3.4.2

In Example 3.32, when we finished processing the input symbols, we move to one of the final states $p_{a}$ or $p_{b}$ if the stack is nonempty. Show that the two separate states are necessary. That is, suppose we merge states $p_{a}$ and $p_{b}$ of Figure 3.15 into a single final state $p$ , with the instructions

\delta (s, \varepsilon , a)=\delta (s, \varepsilon , b)=\delta (p, \varepsilon , a)=\delta (p, \varepsilon , b)=(p, \varepsilon )

Show that, then, the new PDA would accept some strings not in $L$ .

?

Problem 3.4.3

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

Show that each of the following variations of the pushdown automaton model is equivalent to our original definition of pushdown automata, in the sense that the class of languages accepted by pushdown automata remains the same.

?

(a)

The PDA is allowed to push two stack symbols into the stack in one move; that is, the transition function $\delta$ is a function of the following form:

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

(b)

The PDA is allowed to push any number of stack symbols into the stack in one move; that is, the transition function $\delta$ is a function of the following form:

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

(c)

The PDA is required to pop up the top element of the stack at each move and is allowed to push two stack symbols into the stack in one move; that is, the transition function $\delta$ is a function of the following form:

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

(We assume that the PDA starts with a special symbol $ in the stack, i.e., the initial configuration is ( $s, x, \$$ ).)

(d)

The PDA accepts an input string as long as it reaches a final state after it finishes reading the input symbols (regardless of whether the stack is empty or not); that is, the PDA accepts a string $x \in \Sigma^{*}$ if $(s, x, \varepsilon ) \vdash^{*}(q, \varepsilon , \gamma )$ for some $q \in F$ and some $\gamma \in \Gamma^{*}$ .

Problem 3.4.4

(a)(b)

A PDA $M=(Q, \Sigma , \Gamma , \delta , s, F)$ is a deterministic $P D A$ if no configuration of $M$ has more than one successor configuration (but a nonfinal configuration may have no successor). For each of Examples 3.28-3.33, do the following:

?

(a)

Determine whether the PDA given in the example is deterministic or not.

(b)

If the answer to (a) is no, then determine whether there is an equivalent deterministic PDA accepting the same language. If yes, present your deterministic PDA; if no, show why not. [Hint: One way of eliminating (part of) nondeterminism in a PDA is to use the PDA model of Exercise 3(c).]