Chomsky Normal Form

Chomsky Normal Form

A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form-

1. S → AB 
2. A → a

S,A,B are non-terminals and a is a terminal.

Above points can be, as

1. Non-terminal -> two non terminals
2. Non-terminal -> terminal

Example,

S -> AB

A -> a

B -> b

Above grammar is in CNF, because it all productions follow the above wo points of CNF.

What if grammar is not in CNF?

1. Eliminate null productions
2. Eliminate unit productions
3. Eliminate unused production.

Find the grammar in Chomsky Normal form equivalent to S-->aAD;A->aB/bAB;B->b,D->d ?

Ans. Click here.

Related topics :

1. Definition of DFA
2. DFA notations
3. How DFA process inputs
4. DFA solved examples
5. Minimization of DFA
6. Definition of NFA
7. Equivalent of DFA and NFA
8. Properties of transition functions
9. Trape/ Dead state
10. Moore machine
11. Mealy machine
12. Mealy to Moore machine conversion
13. Moore to Mealy machine conversion
14. Difference between Mealy and Moore machine
15. Regular expression
16. Regular expression examples
17. Regular expresstion to CFG
18. Regular expression to Regular grammar
19. Ambiguous grammar
20. Leftmost and Rightmost derivations
21. Arden's Law
22. NFA with ∈ moves
23. Construct NFA without ∈ moves
24. NFA with ∈ to DFA Indirect method
25. Context Free Grammars
26. Convert CFG in to CNF
27. CFL are not closed under intersection