Computation - CFG to DFA

CFGs to DFAs

Hopefully you should remember what a CFG consists of. That is:

• A set of terminal symbols. That is, some given alphabet.


• A set of non-terminal symbols.


• A start state – S.

In order to be able to convert a CFG into a DFA, first you need to identify some key features. This is, the alphabet, the states and the accepting states. Basically we have this:

• The alphabet Σ = the set of terminal symbols from the grammar.


• The states Q = the set of non-terminal symbols (Ξ) from the grammar.


• The start state q• = the non-terminal symbol S.


• The accepting state(s) is the non-terminal symbol(s) that the grammar can end on – ie, they can be transformed into a word that doesn’t contain a non-terminal symbol character.

An Example

Let’s say you were given the context-free grammar if: (yes its basic, but you should get the general idea hopefully…)

S --> aT

T --> aT | bT | ε

Looking at that grammar, we can see that:

• Non-terminal symbols, Ξ = {S, T}  =>  set of states, Q = {S, T}


• We have the terminal symbols, Σ = {a, b}  =>  some alphabet, Σ = {a, b}


• We have a finishing, or an accepting state, F = {T}. This is because the grammar ends on the non-terminal symbol, T.


• We have a start state, S = {S}.

Now we can form the DFA that governs the same CFG:



The transition states that you see are I hope obvious as to why they are? As you can see, we have in the grammar: S --> aT, so we need the transition label of ‘a’ to get to state ‘T’. Then for the set T --> aT | bT | ε, we need a looping transition edge of ‘a, b’ back to state ‘T’. We don’t need to both with the epsilon because this is a DFA not an NFA :P

AND, hopefully. That is it!