8.2 Finite State Machines and Automata

Consider a login system that accepts a username and a password. The FSM might have the following states: Start, UsernameEntered, PasswordEntered, Authenticated, Error.

The transitions depend on user input. For example:

• From Start, entering a valid username moves to UsernameEntered
• From UsernameEntered, entering a valid password moves to Authenticated
• Invalid input at any stage moves to Error

This FSM models the logic of a login system and ensures that only valid input sequences result in authentication.

The following transition diagram is for an FSM that accepts binary strings ending in 01.

For example, the string 11001001, enters at state [latex]q_{0}[/latex] and then transitions through states

[latex]q_{0}(1), q_{0}(1), q_{1}(0), q_{1}(0), q_{2}(1), q_{1}(0), q_{1}(0), q_{2}(1)[/latex]

and the string is accepted. On the other hand, the string 11001000 transitions through states

[latex]q_{0}(1), q_{0}(1), q_{1}(0), q_{1}(0), q_{2}(1), q_{1}(0), q_{1}(0), q_{1}(0)[/latex]

and is not accepted.

Suppose the alphabet is the finite set of symbols [latex]\{ 0, 1 \}[/latex] and the input string is a sequence like 0101, 111, or 000. The machine reads the input string from left to right and, based on the current state and the symbol read, moves to the next state.

Let’s define an FSA that takes a binary input string and outputs a string where each symbol indicates whether the number of 1s seen so far is even (E) or odd (O). The states are [latex]q_{\text{even}}[/latex] and [latex]q_{\text{odd}}[/latex]. The alphabet has input {0, 1} and output {E, O}. The start state is [latex]q_{\text{even}}[/latex]. The transitions are as follows:

• [latex]q_{\text{even}}[/latex] with input 0[latex]\rightarrow q_{\text{even}}[/latex] with output E
• [latex]q_{\text{even}}[/latex] with input 1[latex]\rightarrow q_{\text{odd}}[/latex] with output O
• [latex]q_{\text{odd}}[/latex] with input 0[latex]\rightarrow q_{\text{odd}}[/latex] with output O
• [latex]q_{\text{odd}}[/latex] with input 1[latex]\rightarrow q_{\text{even}}[/latex] with output E

The transition diagram is shown below.

As an example, consider the input string 1010. The following processing occurs:

• Start at [latex]q_{\text{even}}[/latex]
• Read 1: move to [latex]q_{\text{odd}}[/latex], output O
• Read 0: stay in [latex]q_{\text{odd}}[/latex], output O
• Read 1: move to [latex]q_{\text{even}}[/latex], output E
• Read 0: stay in [latex]q_{\text{even}}[/latex], output E

Let’s define a DFA that accepts binary strings with an even number of 0s.

The states are [latex]q_{\text{even}}[/latex] and [latex]q_{\text{odd}}[/latex]. The alphabet is [latex]\Sigma[/latex] = {0, 1}.

The transitions are [latex]\delta (q_{\text{even}},[/latex]0[latex]) = q_{\text{odd}}[/latex], [latex]\delta (q_{\text{even}},[/latex]1[latex]) = q_{\text{even}}[/latex], [latex]\delta (q_{\text{odd}},[/latex]0[latex]) = q_{\text{even}}[/latex], and [latex]\delta (q_{\text{odd}},[/latex]1[latex]) = q_{\text{odd}}[/latex].

The start state is [latex]q_{\text{even}}[/latex]. The accepting state is [latex]q_{\text{even}}[/latex].

The transition diagram is shown below.

Consider the DFA in Example 8.16 that accepts strings ending in 01. The input string 1101 is processed as follows:

• Start at [latex]q_{0}[/latex]
• Read 1: stay at [latex]q_{0}[/latex]
• Read 1: stay at [latex]q_{0}[/latex]
• Read 0: move to [latex]q_{1}[/latex]
• Read 1: move to [latex]q_{2}[/latex]

Since the automaton ends in [latex]q_{2}[/latex], which is an accepting state, the string 1101 is accepted.

Using the same DFA as Example 8.16, the automaton accepts the string 1101 because it ends in the accepting state [latex]q_{2}[/latex]. It does not accept the string 1110 because it ends in [latex]q_{1}[/latex], which is not an accepting state. We describe the automaton's behaviour as accepting all strings that end in 01.

Suppose we want to represent the language of all binary strings that contain an even number of 0s. We could use the DFA in Example 8.19. The structure of the automaton models the rules of the language.

The states are [latex]q_{0}[/latex], [latex]q_{1}[/latex], and [latex]q_{2}[/latex]. The alphabet is [latex]\Sigma[/latex] = {0, 1}.

The transitions are [latex]\delta (q_{0},[/latex] 0[latex]) = \{ q_{0}, q_{1} \}[/latex], [latex]\delta (q_{0},[/latex] 1[latex]) = \{ q_{0} \}[/latex], and [latex]\delta (q_{1},[/latex] 1[latex]) = \{ q_{2} \}[/latex].

The start state is [latex]q_{0}[/latex]. The accepting state is [latex]q_{2}[/latex].

This NFA accepts any string that ends in 01.

Define a language [latex]N[/latex] consisting of all binary strings that end in 01 as in Example 8.23. This NFA accepts strings ending in 01 by nondeterministically guessing the start of the 01 suffix.

Define a language [latex]D[/latex] that accepts binary strings ending in 01 as in Example 8.16. This DFA deterministically tracks the last two symbols to check if they form 01.

Even though the NFA uses nondeterminism and the DFA uses deterministic transitions, both automata accept the same set of strings, those ending in 01. Therefore, they are equivalent.