CODEWITHSUNDEEP
regexfinite-automataautomata
mjuopperi
mjuopperi

Reputation: 971

Constructing a Regular Expression from a Finite Automata

I'm trying to construct a regular expression from a Finite Automaton but found my self completely stuck with this one. The regex to use is like this:

? = 0 or 1
* = 0 or more
+= 1 or more
| = or
_ = empty string
@ = empty set
() = parentheses

As I understand the strings must either be "b*" end with "a*" or end with "a+bb+"
What i have now is ((b*(a+(bb))*)*) but that doesn't take into account a string ending with 'a'.

As said, I'm 100% stuck with this and just can't get my head around how I am supposed to work with this.

image: http://img593.imageshack.us/img593/2563/28438387.jpg

CODE:
Type of the automaton
FA

States
q1
q2
q3
q4

Alphabet
a
b

Initial state
q3

Final states
q3
q4

Transitions
q1 a q2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

Any solutions or tips appreciated!

Upvotes: 0

Views: 1704

Answers (2)

akim
akim

Reputation: 8759

If you feed this to tools for automata (e.g., Vcsn), you'd get this:

In [1]: import vcsn

In [2]: %%automaton a
   ...: $  -> q3
   ...: q1 -> q2 a
   ...: q1 -> q3 b
   ...: q2 -> q2 a
   ...: q2 -> q2 b
   ...: q3 -> q4 a
   ...: q3 -> q3 b
   ...: q4 -> q4 a
   ...: q4 -> q1 b
   ...: q3 -> $
   ...: q4 -> $
   ...: 
mutable_automaton<letterset<char_letters(ab)>, b>

In [3]: a.expression()
Out[3]: (b+aa*bb)*(\e+aa*)

where \e denotes the empty string. Then it's only a problem of syntax conversion.

Graphically:

Vcsn graphical rendering

See this example live, and toy with it.

Upvotes: 2

Laurence Gonsalves
Laurence Gonsalves

Reputation: 143154

It isn't possible to get from q2 to a final state. Remove it and the resulting DFA should be easier to convert.

As I understand the strings must either be "b*" end with "a*" or end with "a+bb+" What i have now is ((b*(a+(bb)))) but that doesn't take into account a string ending with 'a'.

Imagine q3 was not a final state, and q4 was the initial state. What would the regex look like then? Changing that into what you want shouldn't be too hard, just don't be afraid to have the same state and/or transitions described by more than one part of the regex.

One more hint: I'm pretty sure you're going to need to use either ? or | at least once.

Upvotes: 0

Related Questions