CS 4384 — Automata Theory, Homework 4

Download PDF

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.