Featured post
regex - Constructing a Regular Expression from a Finite Automata -
i'm trying construct regular expression finite automaton found self stuck one. regex use this:
? = 0 or 1
* = 0 or more
+= 1 or more
| = or
_ = empty string
@ = empty set
() = parentheses
as understand strings must either "b*" end "a*" or end "a+bb+"
have ((b*(a+(bb))*)*)
doesn't take account string ending 'a'.
as said, i'm 100% stuck , can't head around how supposed work this.
image: http://img593.imageshack.us/img593/2563/28438387.jpg
code:
type of automaton
fa
states
q1
q2
q3
q4
alphabet
a
b
initial state
q3
final states
q3
q4
transitions
q1 q2
q1 b q3
q2 q2
q2 b q2
q3 q4
q3 b q3
q4 q4
q4 b q1
any solutions or tips appreciated!
it isn't possible q2 final state. remove , resulting dfa should easier convert.
as understand strings must either "b*" end "a*" or end "a+bb+" have ((b*(a+(bb)))) doesn't take account string ending 'a'.
imagine q3 not final state, , q4 initial state. regex then? changing want shouldn't hard, don't afraid have same state and/or transitions described more 1 part of regex.
one more hint: i'm pretty sure you're going need use either ?
or |
@ least once.
- Get link
- X
- Other Apps
Comments
Post a Comment