Register

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

• edited by
779 views
1 votes
1 votes

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 \}$.

  1. Give a PDA that recognizes $B$.
  2. Give a CFG that generates $B$.
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
1
admin asked Oct 12, 2019
239 views
Michael Sipser Edition 3 Exercise 2 Question 55 (Page No. 159)
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$
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 \...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 12, 2019
241 views
Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)
Show that every DCFG generates a prefix-free language.
Show that every DCFG generates a prefix-free language.
User Avatar
Link Copied!