CODEWITHSUNDEEP
regexdiscrete-mathematicsfinite-automata
andandandand
andandandand

Reputation: 22270

How do I build this finite automaton?

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

Answers (4)

Stephan202
Stephan202

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:

  • I assume the * means '0 or more times'. However, one of the strings with sum >= 3 must occur. It's say you need a + ('1 or more times').
  • 112 and 211 are missing in the list of strings with sum >= 3.
  • 222 and 2222 in that list are superfluous.
  • All of these strings may be arbitraryly interspersed with 0s.
  • The sum of 00 is no more even than the sum of 0.

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

bayer
bayer

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

poundifdef
poundifdef

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

andandandand
andandandand

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

Related Questions