Search code examples
automationautomaton

A finite automaton accept no string

How can a finite automaton over(0,1) doesn't accept any string? I only can think of 

s->a->q->F

Where the final state F is empty set. Is that true please?

Solution

  • The answer is most likely yes. Why "most likely"? Well.

    Mathematically, an FSA is a 5-tuple (Sigma, S, s0, delta, F), where

    • Sigma is the alphabet,
    • S is the set of states,
    • s0 is the initial state,
    • delta is the state-transition function,
    • F is the set of accepting states.

    Since you fixed Sigma, there are only four places where it can go wrong. If you create your FSA by hand, you of course create one

    • that has no states
    • that has no initial state
    • in which not all states are accessible
    • that has no accepting states

    If we assume a well-formed FSA (meaning S is not empty and s0 in S, all states are accessible), which is the case if you create it from e.g. a regular expression with a library like foma, then yes: the only way for the FSA to not accept any string is to have no accepting states.