Theory of Computation Question


by Opso
Tags: computation, theory
Opso
Opso is offline
#1
Jan28-11, 12:56 PM
P: 1
1. The problem statement, all variables and given/known data

Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is {0,1}.

{w | w has length at least 3 and its third symbol is a 0}

2. Relevant equations

If the final state only has one circle it is rejected, if two, accepted.

3. The attempt at a solution



I am just wondering if this is the most efficient way of doing this problem, or do I have too many states?

Oh also, I forgot to add an arrow pointing to qs indicating the start.
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
verty
verty is offline
#2
Jan29-11, 04:55 PM
HW Helper
P: 1,373
I think you'll agree that there may not be less than three states because one needs to track how much of the input has been seen. The only way to do this is to have independent states for the first three characters. Only on the third character may we check for the final 0.

Is another state required? See if you can you argue that because an accepting state is required, and because none of the first three states may be accepting states, a fourth state is necessary.


Register to reply

Related Discussions
Computation of the subbands of a nanowire using KP theory: spurious solutions Atomic, Solid State, Comp. Physics 0
Theory of computation, automata, machines Other Science Learning Materials 0
theory of computation Academic Guidance 1
Computation Question Calculus 4