-----------------------------------

blackrobe

Tue Mar 16, 2010 1:37 am


Theory of Computation: Finite State Machines

-----------------------------------

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

http://img197.imageshack.us/img197/4500/capturebl.jpg

I've simplified it to this:

http://img682.imageshack.us/img682/4342/capture1kl.jpg

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

Tue Mar 16, 2010 3:02 am


RE:Theory of Computation: Finite State Machines

-----------------------------------

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

Tue Mar 16, 2010 12:08 pm


RE:Theory of Computation: Finite State Machines

-----------------------------------

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