Computer Science Canada Theory of Computation: Finite State Machines |
| Author: | blackrobe [ Tue Mar 16, 2010 1:37 am ] |
| Post subject: | 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: 
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 |
|
| Author: | Dan [ Tue Mar 16, 2010 3:02 am ] |
| Post subject: | 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. |
|
| Author: | Prabhakar Ragde [ Tue Mar 16, 2010 12:08 pm ] |
| Post subject: | RE:Theory of Computation: Finite State Machines |
Hint: in the original diagram, rewrite n as the ordered pair (n mod 3, n div 3). |
|