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 😛

AND, hopefully. That is it!

Advertisements

About Badgerati
Computer Scientist, Games Developer, and DevOps Engineer. Fantasy and Sci-fi book lover, also founder of Cadaeic Studios.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: