Theory of Computation: Finite State Machines

[blackrobe]

Hey, I need someone to help me with this..I'm dying to find out what this DFA do:



I've simplified it to this:



I just want to know what exactly does it accept (what kind of strings)??

I was thinking something like this:

- If there are no a's then number of b's is divisible by 3
- If there are no b's then number of a's is divisible by 3

or something like:

- Number of a's is number of b's mod 3 and vice versa.

Not sure. Any ideas?

Thanks

[Dan]

It looks like you used JFlap for the minimization, it will also give you the regex and regular grammar:

S -> E
S -> bB
S -> aA
A -> aB
A -> bS
B -> bA
B -> bS


(ab | (b | aa)(ba)*(a | bb))*


I don't see any easily recognizable patters off the top of my head but it is 4:00am. However i did notice this:

a = number of As
b = number of Bs
x >= 0
a >= 0
b >= 0

b = 3x + (a % 3)


This is all assuming your minimization is correct.

[Prabhakar Ragde]

Hint: in the original diagram, rewrite n as the ordered pair (n mod 3, n div 3).