1
$\begingroup$

My textbook asks:

Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different from the leftmost symbol. Construct an accepting FSA.

The answer it provides is below. However, I don't understand how you can have one transition for 0,1 and another for 1 from the same state. What does this mean? answer to the problem

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The FA in the image is an NFA as clearly a DFA cannot have more than one move for a symbol from a particular state. Also, it doesn't have any moves for state $q_5$ nor for $q_{10}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But in state q1, why are there two options for where to go if the symbol is '1'? How does this work? $\endgroup$
    – Casper C.
    Mar 12, 2019 at 5:02
  • 1
    $\begingroup$ Question asks to construct an accepting FSA(Finite State Automata) so it can be a DFA or a NFA, hence answer given as NFA. As it's easier to draw for this question. $\endgroup$
    – simple-sober
    Mar 12, 2019 at 5:11
  • $\begingroup$ @CasperC. You seem to be unfamiliar with NFAs, which are FSAs precisely allowing two or more transitions from the same state with the same label. A NFA accepts a string if there is some way to move from the starting state to a final state using the input string. Note that there might be multiple paths you can take, but as long as at least one path reaches a final state, the string is accepted. $\endgroup$
    – chi
    Mar 12, 2019 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.