search
Log In
0 votes
37 views
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without $\epsilon$-rules passes the simplified DK-test iff it is a DCFG.
in Theory of Computation 37 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
20 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$
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 20 views
0 votes
0 answers
2
28 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).
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 28 views
0 votes
0 answers
3
135 views
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$.
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 135 views
0 votes
1 answer
4
66 views
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1’s}}$ $\text{{w| w starts and ends with the same symbol}}$ $\text{{w| the length of w is odd}}$ $\text{{w| the length of w is odd and its middle symbol is a 0}}$ $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
asked May 1, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
...