views:

699

answers:

4

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.

+7  A: 
Stephan202
You did get the notation right. Yes, one with the sum >=3 must have a +, you're right, and those 112 and 211 string are indeed missing. I think I'll add 0* in between the strings. I´ll post the thing below.
omgzor
A: 

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.

omgzor
+2  A: 
rascher
A: 

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.

bayer