Search code examples
computer-sciencefinite-automata

Creating a deterministic finite automata

I need to create a non-empty DFA over the language {a,b,c} with the following properties:

  1. First symbol is a.
  2. Has an even number of b's.
  3. Last symbol is a c.

I was just wondering, should I create 3 seperate automatas, and then combine them using intersections, or should I just create the one, and if that is the case, how can it has an even number of b's? I know I can alternate the states, but not sure how to do it with it all combined.

Thanks

Solution

  • Here's your automaton (assuming that 0 is even and therefor 0 b's is ok):

    [start](a) -> [1]
[start](b,c,<eoi>) -> [reject]

[1](a) -> [1]
[1](<eoi>) -> [reject]

[1](c) -> [2]
[1](b) -> [3]

[2](<eoi>) -> [accept]
[2](c) -> [2]
[2](a) -> [1]
[2](b) -> [3]

[3](<eoi>) -> [reject]
[3](a,c) -> [3]
[3](b)->[1]

    Where is "end-of-input".

    State 1: even number of b's, the last symbol processed not c. State 2: even number of b's, the last symbol processed is c. State 3: odd number of b's.