TOC Finite Automata

The computation power of this model is rather weak. Because it can only use a limited (finite) memory. But it is also useful in some applications.

DFA

Deterministic finite automata

A deterministic finite automata (DFA) is a 5-tuple , where

  • is a finite set called states,
  • is a finite set called alphabet,
  • is the transition function,
  • is the start state (also called initial state), and
  • is the set of accept states (final states).

The transition function can also be represented as a transition table.
The table has rows and columns.
The value in each entry is a state.
is a total function. So, every entry has a value.
The input of a DFA is a string in the language .
The output of a DFA is only accept or reject.

Suppose is a string in . The DFA accepts if and only if:

Each is a state of .
Each is a transition.
is a final state in .

The sequence of transitions can also be expressed as:

Remember, a DFA can be represented as a state graph. The features of the graph are listed:

  • A state is in a circle.
  • A transition is an arc from the current state to the next state.
  • The input symbol required by a transition is the label of the arc.
  • The initial state is pointed by an arrow.
  • Each final state is double circled.

Example

Let be a DFA, where the transition function is:

0 1

0

1

1

0

q0

q1

If is the set of all strings that accepts, then:

  • is the language of machine ;
  • ;
  • recognizes .

For example:

A language is regular if it is recognized by some DFA (Deterministic Finite Automaton).

NFA

Nondeterministic finite automata .

An NFA (Nondeterministic Finite Automaton) is a 5-tuple , where:

  • is the set of states;
  • is the alphabet;
  • is the transition function;
  • is the start state; and
  • is the set of final states.

Suppose is an NFA to recognize the language .

  • If is a string in the language :

    • Then there exists a "way" to reach the final state;
    • It's also possible to reach a non-final state.

  • But if is not a string in the language :

    • Then there is no way to reach the final state.

Please pay attention to the quantifiers.

Different between DFA and NFA

The difference between a DFA and an NFA is the transition function .

  • DFA:
  • NFA:
    • is the power set of .

This difference allows:

  • One state to transition to zero, one, or multiple states by taking one input symbol.

Automatas can be further upgraded by a special transition.

An is a transition from one state to another state by taking no input symbol.

Such automata is defined.

NFA with

An NFA with ε-moves is the same as an NFA (without ε-moves) except the transition function:

Later, we will see that ε-moves allow us to recursively construct NFAs, which is... elegant.

Equivalence of DFA and NFA

Power

Let and be two computation models. is as powerful as if:

  • For all languages , is recognized by some machines in if and only if it is recognized by some machines in .

is more powerful than if there is a language which can be recognized by some machines in but no machine in .

Note: A computation model is a set of all machines of the same type.

Theorem

DFA, NFA, and NFA with -moves are of the same computation power.

For convenience, we denote the ordering on the power by , , , etc. Trivially,

Lemma

Next, we only need to show .

It seems the content repeats the explanation for converting to a DFA and introduces the concept of -closure more formally. Here's a summary in Markdown format for your reference:

The Intuition of the Proof:

  • For every , we can construct a DFA that recognizes the same language.
  • This is equivalent to the process of converting an NFA to an equivalent DFA.
Def: -closure

Let be an .
The -closure of a state , denoted , is defined as:

  • represents the set of all states that can be reached starting from only using -transitions.
  • This closure includes itself and any other states reachable via one or more -moves.
  • Alternative Name: The -closure is sometimes referred to as the Kleene Star or Kleene Closure.
Def: ε of a Set of States

Let be a set of states for a given NFA. The -closure of , denoted , is:

This means the -closure of is the union of the -closures of all individual states in .
is the set of states reachable from using only -transitions.

Def: -Move of a Set of States:

Let be a set of states, and let be a symbol for a given NFA. The -move of , denoted , is:

This describes all the states reachable by:

  1. First making an -transition from any state in , and
  2. Then taking all -transitions from those resulting states.

NOTE: gives the set of states reachable by consuming the symbol .

Construction Algorithm

Let be an . We construct a DFA , where:

  • such that:

States ():

  • , the power set of .
  • Each state in is a subset of the states in .

Transition Function ():

, defined as:

  • For each state and symbol :
  • Find all states reachable by an -move from some , considering -closures.

Start State ():

  • , the -closure of the initial state of .

Final States ():

  • .
  • A subset of states is a final state in if it includes any final state of .

Ensures captures all possible behaviors of , including -transitions.
Uses the power set of as the state space to simulate nondeterminism deterministically.

Pseudocode

Algorithm Convert NFAε_\varepsilon to DFA

Input: An NFAε_\varepsilon N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F)

Output: A DFA D=(Q′,Σ,δ′,q0′,F′)D = (Q', \Sigma, \delta', q_0', F')

Q′←{E(q0)}Q' \gets \{E(q_0)\}, E(q0)E(q_0) is unmarked, and δ′←∅\delta' \gets \emptyset

while there exists an unmarked state R∈Q′R \in Q' do

Mark RR

for each symbol a∈Σa \in \Sigma do

U←E(δ(R,a))U \gets E(\delta(R, a))

if U∉Q′U \notin Q' then

Add UU to Q′Q'

end if

Add δ′(R,a)=U\delta'(R, a) = U to δ′\delta'

end for

end while

q0′←E(q0)q_0' \gets E(q_0)

F′←{R∣R has a final state in F}F' \gets \{R \mid R \text{ has a final state in } F\}

return D←(Q′,Σ,δ′,q0′,F′)D \gets (Q', \Sigma, \delta', q_0', F')

Example

Let’s try to convert this to .

1

0

0, 1

0

ε

start

q0

q1

q2

Initially

Suppose the unmarked states are red.

start

{q0, q2}

Step 1


0

1

start

{q0, q2}

{q1}

Step 2


0

1

0

1

start

{q0, q2}

{q1}

{q1, q2}

{q2}

Step 3


0

1

0

1

0

1

start

{q0, q2}

{q1}

{q1, q2}

{q2}

{q0, q1, q2}

Step 4


0

1

0

1

0

1

0

1

start

{q0, q2}

{q1}

{q1, q2}

{q2}

{}

{q0, q1, q2}

Step 5


0

1

0

1

0

1

0

1

0

1

start

{q0, q2}

{q1}

{q1, q2}

{q2}

{}

{q0, q1, q2}


0

1

0

1

0

1

0

1

0, 1

0

1

start

{q0, q2}

{q1}

{q1, q2}

{q2}

{}

{q0, q1, q2}

Finally

and are final states.

Rename the states to make the DFA more readable and beautiful: .

0

1

0

1

1

0

1

0

0

0, 1

start

q'0

q'1

q'2

q'3

q'4

q'5

is a trap state because it has no valid transitions.

Table Of Contents
TOC Finite Automata
DFA
NFA
Different between DFA and NFA
Equivalence of DFA and NFA
Power
Construction Algorithm
Pseudocode
Example
Initially
Step 1
Step 2
Step 3
Step 4
Step 5
Finally