Register

Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)

• edited by
1,952 views
0 votes
0 votes

Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$

  • $A\rightarrow BAB \mid B \mid \epsilon$
  • $B\rightarrow 00 \mid \epsilon$
• edited by
User Avatar

1 Answer

1 votes
1 votes
CNF doesn't allows ε-productions

first we've to eliminate ε-productions

A->B | AB | BA | BB | ε

B->00

the language contains ε so A->ε can't be eliminated

Eliminating unit productions

A->00 | AB | BA | BB | ε

B->00

Now converting to CNF

A->CC | AB | BA | BB | ε

B->CC

C->0
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
admin asked May 4, 2019
506 views
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w....
User Avatar
0 votes
0 votes
1 answer
2
admin asked May 4, 2019
369 views
Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
User Avatar
0 votes
0 votes
1 answer
3
admin asked May 4, 2019
267 views
Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
User Avatar
Link Copied!