Wednesday 9 September 2009

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:

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!

No comments:

Post a Comment