Register

Ullman--Chomsky Normal Form

1,165 views
0 votes
0 votes
If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it.

S->ASB|epsilon

A->aAS|a

B->SbS|A|bb
User Avatar

1 Answer

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

Related questions

0 votes
0 votes
0 answers
1
Sanjay Sharma asked Dec 10, 2017
806 views
Chomsky Normal Form
User Avatar
2 votes
2 votes
1 answer
2
Veeplob Singh asked Jul 3, 2017
844 views
Raghunath Tiwari(NPTEL NOC Chomsky Normal Form)
S->ASB A->aASA | a | ϵ B->SbS | A | bb Convert this grammar into Chomsky Normal Form
S->ASBA->aASA | a | ϵB->SbS | A | bbConvert this grammar into Chomsky Normal Form
User Avatar
1 votes
1 votes
2 answers
3
Anjan asked Jan 1, 2018
2,987 views
Chomskey Normal Form
State true/false In CNF , S-> espilon and Start symbol can appear on RHS side of production.
State true/falseIn CNF , S- espilon and Start symbol can appear on RHS side of production.
User Avatar
1 votes
1 votes
1 answer
4
admin asked May 4, 2019
514 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
Link Copied!