# Michael Sipser Edition 3 Exercise 2 Question 55 (Page No. 159)

43 views

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

• $R \rightarrow S \mid T$
• $S \rightarrow aSb \mid ab$
• $T \rightarrow aTbb \mid abb$

## Related questions

1
50 views
Let G be the following grammar: $S \rightarrow T\dashv$ $T \rightarrow T aT b \mid T bT a | \epsilon$ Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers of a’s and b’s} \}$. Use a proof by induction on the length of $w$. Use the DK-test to show that G is a DCFG. Describe a DPDA that recognizes L(G).
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.