Transforming Regular Grammars to Equivalent Finite State Automata

Algorithm

The algorithm now follows:

  1. construct an -free regular grammar G' from G (see relevant section);
  2. create a FSA M, with a state for every non-terminal in G'. Set the state representing the start symbol to be the start state;
  3. add another state D, which is terminal;
  4. if the production S is in G' (where S is the start symbol of G', set the state representing S to be final;
  5. for every production AaB in G, add a transition from state A to state B labelled with terminal a;
  6. for every production Aa in G, add a transition from A to the terminal state D

Example

Construct a FSA M that recognises the language generated by the following regular grammar G:

S a | aA | bB |
A aA | aS
B cS |

where S is the start symbol.

  1. Construct an equivalent -free grammar:

    S1 a | b | aA | bB |
    S a | b | aA | bB
    A a | aA | aS
    B c | cS

    where S1 is the start symbol.

  2. create a FSA M, with a state for every non-terminal in G' - {S1, S, A, B}. S1, being the start symbol is set to be the start state:

  3. add another terminsl state D0:

  4. since S1 was in the grammar, state S1 is also set to be final:

  5. for every rule of the form AaB, we add a transition from state A to state B labelled a:

  6. for every rule of the form Aa, we add a transition from state A to state D0 labelled a:

Exercises

Construct finite state automata equivalent to the following regular grammars:

  1. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC,
    A aA | bB | ,
    B bB | b | ,
    C cB | cC | },
    S >
  2. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC | ,
    A aA | aS,
    B b,
    C cB | cS },
    S >
  3. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC | ,
    A aA | aS,
    B b,
    C cB | cS },
    S >
  4. G = < { a, b },
    { S, A },
    {S aA | bS,
    A },
    S >
  5. G = < { a },
    { S },
    { S},
    S >