# Computation – CFG to DFA

September 9, 2009 Leave a comment

## 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 😛

AND, hopefully. That is it!