some homework help (automata/regular expressions)

doomgiver

Warframe
YuGzq.jpg


this is the non finite automata

the one state at the top with triangle is the start state
the one on the right bottom is the end state.

i want to describe it with a regular expression.


solutions i thought of :

abc((dbc)*+(febc)*)fg

it will go from a-b-c, then it can branch as many times as it wants in d-b-c, or it can branch f-e-b-c, then it ends as f-g

other two possible :

abc((dbc)+(febc))*fg
abc((d+fe)*bc)fg


()* shows that it is repeated many times , + means OR.

any help?
 

rhlravi

Broken In
solution: a(bcd+bcef)*bcfg

why your 1st solution is wrong: only dbc loop or febc loop, not both.

why your 2nd solution is wrong: messed up ordering in the loop. even if you correct the order, it wont end with bcfg. add bc before the end, not at start.

why your 3rd solution is wrong: loops of only d or fe are also possible in that solution.
 
Last edited:

mitraark

Siuuu
a(bcd+bcfe)*bcfg , very well done rhlravi !

WHen I looked at the program the first solution that came to my mind was

a (bcd)*+(bcf(e+g))* --> WRONG :D

Automata is an AWESOME Subject , 1st three months of the semester , i didn;t understand anything :D , and when i finally began to get it , i liked it more :)
 
Top Bottom