Chomsky Normal Form (CNF) Converter
This script can be used to convert a Context Free Grammar (CFG) to Chomsky Normal Form (CNF).
The implementation is based on the theory provided in the book ''Elements of the Theory of Computation (2nd Edition)", by Harry Lewis and Christos H. Papadimitriou.
###Theory
According to the book, the right hand side of the rule in a CFG in Chomsky Normal Form must have length two.
So, there are 3 kind of rules that need to be removed/replaced:
- Long rules (eg. A->BCD)
- Empty rules (eg. A->e)
- Short rules (eg. A->a)
Input
User's input include:
- Number of rules
- Initial state
- Rules, each on in a space-delimited form (A BC, for A->BC)
Example
Here 's an example indicating how to use the script:
| Message | User Input |
|---|---|
| Give number of rules | 3 |
| Give initial state | S |
| Rule #1 | S SS |
| Rule #2 | S (S) |
| Rule #3 | S e |