CS 4384 — Automata Theory, Homework 4
Construct a CFG for the DFA below
Convert the following CFG G into an NFA that accepts L(G)
First, we must observe that this is a regular grammar. If it was not, then there would be no NFA that accepts L(G) Following the steps to convert a CFG for a regular grammar into an NFA, we can see that the CFG is equivalent to the following NFA:
Eliminate -productions from the grammar below
Here we must eliminate the rule . To remove this, we add the following rules:
In other words, for each rule that involved C, we added a rule substituting with .
This gives the final CFG
Eliminate chain productions from the grammar below
We must eliminate the rules
To do this, we simply replace these as follows:
Since we now have the rule , we must apply the same procedure again to get
Taking these together, we get
Convert the following grammar to Chomsky Normal Form
Next, we must remove all -productions
Removing the rule we get
Removing the rule we get
There are no chain productions to remove
Finally, we create new variables and rules as follows
Every variable is now of the form or , and the CFGs are equivalent, thus the grammar is now in CNF.