Register

#self doubt

203 views
0 0 votes

Start symbol generating ε. (e.g.; S-> ε)
and also written 

  • Any Context-free Grammar without ε in its language has an equivalent CNF.

source - https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/

I read the below page but still not getting clearance in doubt, S->null is allowed but language containing null will not contain equivalent CNF. 
can someone explain this?

https://gateoverflow.in/188159/chomskey-normal-form

1 Answer

0 0 votes

You are right. In general, ϵ is not allowed in the CNF form of grammars.

But there is one exception in CNF - If the language itself contains an empty string. If that is the case then we have to make a new start symbol S' and write its production as

S' -> S | ϵ

Also refer https://cs.stackexchange.com/a/92411

Voting & Accepting an answer helps improve the community
← Previous · Expression Evaluatio...Next → · Pipelining
← Previous in category · GO Classes GATE CS |...Next in category → · Decidability and Und...
Position:
Show:

Related questions

0 0 votes
0 0 answers
493
493 views
Dknights asked Jan 16, 2025
493 views
#self doubt
Can someone help in the below language is this regular, how to prove it @Deepak Poonia sir @Shaik Masthan sirNumber of 0s and 1s are equal and in each prefix of w number ...
0 0 votes
1 1 answer
334
334 views
Dknights asked Jan 8, 2024
334 views
#self doubt
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*)Can someone please explain the flow how we will process the language in CFL.
0 0 votes
2 2 answers
670
670 views
Dknights asked Dec 23, 2023
670 views
#self doubt
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
0 0 votes
1 answers 1 answer
1.4k
1.4k views
Sunnidhya Roy asked Dec 12, 2022
1,359 views
#Self Doubt
L = {0^n 1^2n 0^n+m , n,m>=0}Is this Language CFL or non CFL?According to mewe can write this as 0^n 1^n 1^n 0^n 0^mThen we will keep on pushing 0’s and as and when we ge...