1

I know how to convert regular expression into FSM but not exactly sure how to reverse it.

enter image description here

what would the regular expression for this example be?

user2316675
  • 263
  • 1
  • 3
  • 9
  • Read my this answer [Regular Expression to DFA](http://stackoverflow.com/questions/13770814/drawing-minmal-dfa-for-the-given-regular-expression/14024179#14024179) and [to write regular expression for a DFA](http://stackoverflow.com/questions/7550711/what-is-the-language-of-this-deterministic-finite-automata/13965717#13965717) – Grijesh Chauhan May 30 '13 at 18:35
  • thank you will give it a read – user2316675 May 30 '13 at 18:36
  • um.. but the number of a has to be even for it to get to final state right? how would you represent that? – user2316675 May 30 '13 at 18:39

1 Answers1

2

Regular expression for your DFA will is (b + ab*a)*

The language description: Symbol b can appear in any fashion but restriction is a can to be for even number of times in language strings.

(b + ab*a)*
   ^   ^  ^
   |   |  "* because loop on initial state"  
   |   | "* on b because of self loop with label b on 2nd state"
   |
   |"+ because two outgoing edges, One is self loop other via 2nd state"


Here: + means Union, * means repetition for zero or more times

Note: Language string examples: {^, b, aa, bababb...}

(even as and any bs including null)

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • is there a formula to do this? – user2316675 May 30 '13 at 18:41
  • @user2316675 nop, although there is a formal way to convert a FSM into RE if its in standard from -- technique is known [Arden's Therm](http://books.google.co.in/books?id=fodwUrSC8e0C&pg=SA3-PA7&lpg=SA3-PA7&dq=arden%27s%20theorem%20for%20regular%20language&source=bl&ots=QTuxWbiATB&sig=Rf32daVHvstUV5JyExianv6A4Pw&hl=en&sa=X&ei=sSkZUb-9E8iUrgejlIEw&ved=0CCsQ6AEwBQ#v=onepage&q=arden%27s%20theorem%20for%20regular%20language&f=false). But I prefer analytically way as I explained in my answer I linked with your question. – Grijesh Chauhan May 30 '13 at 18:45
  • yea I was thinking just removing it one by one. but I am scared i get to exam with really complicated fsm and get stuck – user2316675 May 30 '13 at 18:47
  • @user2316675 thought my profile you can go to some answer on theory of computation. If you feels TOC is hard and mathematical [Peter Linz](http://vcetbundi.org/downloads/An%20Introduction%20to%20Formal%20Languages%20and%20Automata.pdf) is the book I suggests to students. Gook Luck for your exam! – Grijesh Chauhan May 30 '13 at 18:51
  • 1
    @user2316675 ok I add a very short explanation here too. – Grijesh Chauhan May 30 '13 at 18:54