Reputation: 22270
I'm studying for a Discrete Mathematics test and I found this exercise which I can't figure out.
"Build a basic finite automaton (DFA,NFA,NFA-lambda) for the language in the alphabet Sigma = {0,1,2} where the sum of the elements in the string is even AND this sum is more than 3"
I have tried using Kleene's Theorem concatenating two languages like concatenating the one associated with this regular expression:
(00 U 11 U 22 U 02 U 20)*
- the even elements
with this one
(22 U 1111 U 222 U 2222)*
- the ones whose sum is greater than 3
Does this make any sense?? I think my regex are flabby.
Upvotes: 2
Views: 2070
Reputation: 61579
I find your notation a bit fuzzy, so perhaps I'm completely misunderstanding. If so, disregard the following. It seems you're not there yet:
Edit: how about this (acc is the only accepting state, dot-source):
automaton http://student.science.uva.nl/~sschroev/so/885411.png
At states a and c the string sum is always odd. At states start, b and acc the sum is always even. Furthermore, at start the sum is 0, at b it is 2 and at d it is >= 4. This can be proved rather easily. Hence the accepting state acc meets all criteria.
Edit 2: I'd say this is a regex which accepts the requested language:
0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+
Upvotes: 9
Reputation: 6904
I find it easier just to think in terms of states. Use five states: 0, 1, 2, EVEN, ODD
Transitions:
State, Input -> New State
(0, 0) -> 0
(0, 1) -> 1
(0, 2) -> 2
(1, 0) -> 1
(1, 1) -> 2
(1, 2) -> ODD
(2, 0) -> 2
(2, 1) -> ODD
(2, 2) -> EVEN
(ODD, 0) -> ODD
(ODD, 1) -> EVEN
(ODD, 2) -> ODD
(EVEN, 0) -> EVEN
(EVEN, 1) -> ODD
(EVEN, 2) -> EVEN
Only EVEN is an accepting state.
Upvotes: 0
Reputation: 19370
Not sure if this is answering your question, but: do you need to submit a regular expression? or will an FSM do?
At any rate, it might be helpful to draw the FSM first, and I think this is a correct DFA:
FSM http://img254.imageshack.us/img254/5324/fsm.png
If that is the case, when constructing your regular expression (which, remember, has different syntax than programming "regex"):
0*
to indicate "0 as many times as you want". This makes sense, since 0 in your string doesn't change the state of the machine. (See, in the FSM, 0 just loops back to itself)
You'd need to account for the different combinations of "112" or "22" etc - until you reach at least 4 in your sum.
If your sum is greater than 3, and even, then (0|2)* would keep you at a final state. Otherwise (sum > 3, and odd) you'd need something like 1(0|2)* in order to put you at an accepting state.
(don't know if this helps, or if its right - but it might be a start!)
Upvotes: 2
Reputation: 22270
Each expression, as guided by Stephan, may be:
(0*U 2* U 11)* - the even sums
with this one
(22 U 11 U 222 U 112 U 211 U 121)+ - the ones whose sum is greater than 3
I don't know if it could be simplfied more, it would help designing the automaton.
Upvotes: 0