Finite Automata

Finite Automata: A deterministic finite automaton (DFA) belongs to a special class of finite automata in which their operation is completely determined by their input as described below. A DFA can be viewed as a simple language recognition device.

An input tape (divided into squares) contains a string of symbols, with one symbol in each tape square. The finite control is the main part of the machine whose internal status can be specified as one of a finite number of distinct states. Using a movable reading head, the finite control can sense the symbol written at any position on the input tape. This reading head is initially pointing to the leftmost square of the input tape and the finite control is set to the initial state. The automaton reads one symbol from the input tape at regular intervals and the reading head moves right to the next symbol on the input tape. Then the automaton enters a new state depending on the current state and the symbol read. These steps repeat until the reading head reaches the end of the input string. If the state reached after reading the entire string is one of the specified final states, the machine is said to accept the input string. The set of strings accepted by the machine is the language accepted by this machine. We now formally define a DFA.

Deterministic Finite Automaton: A deterministic finite automaton A is a 5-tuple Σ, S, S0, F, δ, in which

Σis a finite alphabet,
S is a finite set of states,
S0 ∈ S is the initial state,
F ⊆ S is the set of final states, and
δ is the transition function from S × to S.

We can represent an automaton by a tabular representation called a transition table. For example, the transition table shown in Figure 2.9 represents an automaton that accepts strings in {a, b}∗ with an odd number of bs. ρ is the current input symbol read. s is the current state of the automaton. A clearer graphical representation of an automata is a state transition diagram (or simply state diagram), which is a labeled directed graph. In this graph, nodes represent states, and an edge (transition or arrow) is labeled with the symbol ρ from state s to state s if δ(s, ρ) = s. The initial state is indicated by a > or →. Final states, also called fixed points, are represented by double circles. The state transition diagram for the above automaton is shown in Figure 2.10. Figure 2.11 shows the transition table of an automaton that accepts strings in {a, b}∗ with zero or an odd number of bs followed by zero or an even number of as. Figure 2.12 shows the corresponding automaton.

To make finite automata more expressive, we introduce the feature of nondeterminism. A state change in a nondeterministic finite automaton (NFA) may be only partially determined by the current state and input symbol, and there may be more than one next state given a current state. Every nondeterministic finite automaton can be shown to be equivalent to a deterministic finite automaton, but this corresponding DFA usually contains more states and transitions. Hence, nondeterministic finite automata can often simplify the description of language recognizers.

Nondeterministic Finite Automaton:A nondeterministic finite automaton A is a 5-tuple (Σ, S, S0, F, Δ) in which

Σ is a finite alphabet,
S is a finite set of states,
S0 ∈ S is the initial state,
F ⊆ S is the set of final states, and ,
Δ the transition relation, is a finite subset of S × Σ∗ → S.

The class of languages accepted by finite automata is closed under concatenation, union, complementation, intersection, and Kleene star. We can prove each case by constructing a finite automaton α from one or two given finite automata. A language is regular iff it is accepted by a finite automaton. Let L(α), L(α1), and L(α2) be the languages accepted by automaton α, α1, and α2, respectively.
1. L(α) = L(α1) ◦ L(α2).
2. L(α) = L(α1) ∪ L(α2).
3. Σ∗ − L(α) is the complementary language accepted by deterministic finite automaton α , which is the same as α but with final and nonfinal states interchanged.
4. L(α1) ∩ L(α2) = Σ∗ − ((Σ∗ − L(α1)) ∪ (Σ∗ − L(α2))).
5. L(α) = L(α1)∗.
Several important problems can be stated for finite automata, and the solutions to some of these problems can be derived using these closure properties. These problems are:

1. Given a finite automaton α:
(a) Is string t ∈ L(α)?
(b) Is L(α) = ∅?
(c) Is L(α) = Σ∗?

2. Given two finite automata α and β:
(a) Is L(α) ⊆ L(β)?
(b) Is L(α) = L(β)?
The algorithms for solving the above problems are as follows. Suppose automaton α is deterministic. A nondeterministic finite automaton can always be transformed into a deterministic one.