Chomsky Normal Form
A Grammar is in Chomsky Normal Form if each production rule has one of the following forms:
- A → BC
- A → x
Here A B and C are non terminals. x is a terminal. S is the start symbol of the grammar. Also any non terminal which is not the start state can not be empty. So B and C cannot be S. If its not the start state its not empty.
So what is important is that each non terminal can only be rewritten to a rule with ends in only one terminal. So you can have Ab but not Abb.
This are the bullet points from the slide. A grammar is in CNF if:
- There are no rules generating the empty string
- Rules have either terminals or sequence of two non-terminals as the right-hand side.
You can rewrite any Context free grammars to chomsky normal form. This means you can also rewrite any regular grammar to comsky normal form.
Although I have tried my best to make sure this summary is correct, I will take no responsibility for mistakes that might lead to you having a lower grade.
If you see anything that you think might be wrong then please create an issue on the Github repository or even better, create a pull request 😄
Do you appreciate my summaries, and you want to thank me then you can support me here:
Every model is wrong, but some models are usefull.