Register

Explain This

1,079 views
1 1 vote

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one[note 1] which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.

Source https://en.m.wikipedia.org/wiki/Chomsky_normal_form

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · compiler designNext → · Cache Average access...
← Previous in category · MadeEasy Test Series...Next in category → · theory of computatio...
Position:
Show:

Related questions

1 1 vote
0 0 answers
645
645 views
HenryAsks21 asked May 2, 2022
645 views
Self doubt about CFG to CNF conversion.
I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG: $S \rightarrow bXb \ |\ b...
0 0 votes
1 1 answer
932
932 views
admin asked May 4, 2019
932 views
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is...
1 1 vote
1 1 answer
847
847 views
admin asked May 4, 2019
847 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.$
0 0 votes
1 1 answer
2.6k
2.6k views
admin asked May 4, 2019
2,590 views
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
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 ...