statestate-machinecomputation-theoryfinite-automatadfa

a challenging finite automata - what is the language?

I have this finite automata (FA) and want to write its language. I think its

L={x E {0,1} | {x with subset of 00 and ends in 1} and it would help to know what the type of FA it is.

I think it's a DFA because there is only one transition per state, but the accept state (marked by double rings) is in the middle instead of at the end.

Does this mean state c is never reached and does that make it neither DFA or NFA?

What do you think?

Solution

  • The image shows a state diagram of a deterministic finite automaton (DFA). It is deterministic because for a given input there are no two ways to run through this state diagram.

    but the accept state (marked by double rings) is in the middle instead of at the end.

    There is no requirement that the accept state should be at the end. If it would be required that all transitions from an accept state would have to be to an accept state, then you could only describe languages that will accept any extension of valid input, no matter what you append to it.

    A DFA can describe a language where extending a valid input with more data could make it invalid. For instance, the language over {0,1} that only accepts input that doesn't have a zero, will have a transition to a non-accept state as soon as a 0 is encountered. There can be accept states with outgoing transitions to states that are not accepting. Also the Wikipedia page on DFA includes such state diagrams as examples.

    In your case, state 𝐶 is a sink: it is a non-accept state from which you cannot escape. Once you arrive in that state, you can conclude the input is not valid.

    I think it's L={x E {0,1} | {x with subset of 00 and ends in 1}

    A valid input does not have to end in 1. If from state 𝐴 we read a 0, we get into 𝐵. If the input ends there (with that 0), we have valid input.

    The three states 𝐴, 𝐵, and 𝐶 can be described as follows:

    And so the language of this state diagram are all inputs that include exactly one 0:

          𝐿 = {𝑥 ∈ {0,1}* | 𝑥 includes exactly one 0}

    ...which more formally is:

          𝐿 = {1𝑚01𝑛 | 𝑚, 𝑛 ∈ ℕ0}