Finite Automata and Regular Expressions

FINITE AUTOMATA

A finite automata consists of a finite number of states and a finite number of transitions, and these transitions are defined on certain, specific symbols called input symbols. One of the states of the finite automata is identified as the initial state the state in which the automata always starts. Similarly, certain states are identified as final states. Therefore, a finite automata is specified as using five things:

1. The states of the finite automata;

2. The input symbols on which transitions are made;

3. The transitions specifying from which state on which input symbol where the transition goes;

4. The initial state; and

5. The set of final states.

Therefore formally a finite automata is a five-tuple:

where:

• Q is a set of states of the finite automata,

• Σ is a set of input symbols, and

• δ specifies the transitions in the automata.

If from a state p there exists a transition going to state q on an input symbol a, then we write δ(p, a) = q. Hence, δ is a function whose domain is a set of ordered pairs, (p, a), where p is a state and a is an input symbol, and the range is a set of states.

Therefore, we conclude that δ defines a mapping whose domain will be a set of ordered pairs of the form (p, a) and whose range will be a set of states. That is, δ defines a mapping from

q₀ is the initial state, and F is a set of final sates of the automata. For example:

where

A directed graph exists that can be associated with finite automata. This

graph is called a "transition diagram of finite automata." To associate a graph with finite automata, the vertices of the graph correspond to the states of the automata, and the edges in the transition diagram are determined as follows.

If δ (p, a) = q, then put an edge from the vertex, which corresponds to state p, to the vertex that corresponds to state q, labeled by a. To indicate the initial state, we place an arrow with its head pointing to the vertex that corresponds to the initial state of the automata, and we label that arrow "start." We then encircle the vertices twice, which correspond to the final states of the automata. Therefore, the transition diagram for the described finite automata will resemble Figure 2.1.

Figure 2.1: Transition diagram for finite automata δ (p, a) = q.

A tabular representation can also be used to specify the finite automata. A table whose number of rows is equal to the number of states, and whose number of columns equals the number of input symbols, is used to specify the transitions in the automata. The first row specifies the transitions from the initial state; the rows specifying the transitions from the final states are marked as *. For example, the automata above can be specified as follows:

A finite automata can be used to accept some particular set of strings. If x is a string made of symbols belonging to Σ of the finite automata, then x is accepted by the finite automata if a path corresponding to x in a finite automata starts in an initial state and ends in one of the final states of the automata; that is, there must exist a sequence of moves for x in the finite automata that takes the transitions from the initial state to one of the final states of the automata. Since x is a member of Σ*, we define a new transition function, δ₁, which defines a mapping from Q � Σ* to Q. And if δ₁ (q₀, x) = a member of F, then x is accepted by the finite automata. If x is written as wa, where a is the last symbol of x, and w is a string of the of remaining symbols of x, then:

For example:

where

Let x be 010. To find out if x is accepted by the automata or not, we proceed as follows:

• δ₁(q₀, 0) = δ (q₀, 0) = q₁

• Therefore, δ₁ (q₀, 01 ) = δ {δ₁ (q₀, 0), 1} = q₀

• Therefore, δ₁ (q₀, 010) = δ {δ₁ (q₀, 0 1), 0} = q₁

• Since q₁ is a member of F, x = 010 is accepted by the automata.

• If x = 0101, then δ₁ (q₀, 0101) = δ {δ₁ (q₀, 010), 1} = q₀

• Since q₀ is not a member of F, x is not accepted by the above automata.

Therefore, if M is the finite automata, then the language accepted by the finite automata is denoted as L(M) = {x | δ₁ (q₀, x) = member of F }.

In the finite automata discussed above, since δ defines mapping from Q � Σ to Q, there exists exactly one transition from a state on an input symbol; and therefore, this finite automata is considered a deterministic finite automata (DFA).

Therefore, we define the DFA as the finite automata:

M = (Q, Σ, δ, q₀, F ), such that there exists exactly one transition from a state on a input symbol.