Automata Theory | Deterministic Finite Automata (DFA) | Transition Table | Transition Diagrams | Language of DFA | Theory Of Computation (TOC)

Automata Theory

Automata (singular: automation) are abstract models of machines that perform computations on input by moving through a series of states. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present state. As a result, once the computation reaches an accepting state, it accepts that input. The most general and powerful automata are the Turing machine.

Characteristics of such machines include:

• Inputs: assumed to be sequences of symbols selected from a finite set I. Namely, set I is the set {x1, x,2. x3,...,xk} where k is the number of inputs.
• Outputs: sequences of symbols selected from a finite set Z. Namely, set Z is the set {y1,y2, y3,....,ym} where m is the number of outputs.
• States: finite set Q, whose definition depends on the type of automaton. 

An automaton has a mechanism to read input, which is a string over a given alphabet. This input is actually written on an input tape /file, which can be read by an automaton but cannot change it.
Input file is divided into cells each of which can hold one symbol. Automaton has a control unit which is said to be in one of a finite number of internal states. The automation can change states in
a defined way.

Fig: Diagrammatic representation of a generic automation

There are four major families of automaton:

• Finite-state machine
• Pushdown automata
• Linear-bounded automata
• Turing machine

The families of automata above can be interpreted in a hierarchical form, where the finite-state machine is the simplest automata and the Turing machine is the most complex. The focus of this project is on the finite-state machine and the Turing machine.

States, Transitions, and Finite-State Transition System

A state of a system is an instantaneous description of that system that gives all relevant information necessary to determine how the system can evolve from that point on.

Transitions are changes in states that can occur spontaneously or in response to inputs to the states. Though transitions usually take time, we assume that state transitions are instantaneous (which is an abstraction).

A system containing only a finite number of states and transitions among them is called a finite-state transition system.

Finite State Machines:

An automaton in which the state set Q contains only a finite number of elements is called a finite-state machine (FSM). FSMs are abstract machines, consisting of a set of states (set Q), a set of input events (set I), a set of output events (set Z), and a state transition function. The state transition function takes the current state and an input event and returns the new set of output events and the next state. Therefore, it can be seen as a function that maps an ordered sequence of input events into a corresponding sequence, or set, of output events.

In order to fully understand conceptually a finite-state machine, consider an analogy to an elevator:

An elevator is a mechanism that does not remember all previous requests for service but the current floor, the direction of motion (up or down), and the collection of not-yet satisfied requests for services. Therefore, at any given moment in time, an elevator operated would be defined by the following mathematical terms:

• States: finite set of states to reflect the past history of the customers’ requests.
• Inputs: a finite set of input, depending on the number of floors the elevator is able to access. We can use the set I, whose size is the number of floors in the building.
• Outputs: finite set of output, depending on the need for the elevator to go up or down, according to customers‘ needs.

Applications of Finite State Machines

• Traffic Lights
• Video Games
• Text Parsing
• CPU Controllers
• Protocol Analysis
• Natural Language Processing
• Speech Recognition

Types of Finite Automata:

Finite Automaton can be classified into two types:
Deterministic Finite Automata (DFA)
Non-deterministic Finite Automata (NDFA/ NFA)

Deterministic Finite Automata (DFA)

Deterministic Finite State Automata (DFA) are the simple machine that reads an input string- one symbol at a time- and then, after the input has been completely read, decides whether to accept or reject the input. As the symbols are read from the tape, the automata can change its state, to reflect how it reacts to what it has seen so far.

Thus, a DFA conceptually consists of 3 parts:

• A tape to hold the input string. The tape is divided into a finite number of cells. Each cell holds a symbol from.
• A tape head for reading symbols from the tape
• A control, which itself consists of 3 things:

1. finite number of states that the machine is allowed to be in (zero or more states are designated as accepting or final states),
2. a current state initially set to a start state,
3. a state transition function for changing the current state.

An automaton processes a string on the tape by repeating the following actions until the tape head has traversed the entire string:

• The tape head reads the current tape cell and sends the symbols found there to the control. Then the tape head moves to the next cell.
• The control takes s and the current state and consults the state transition function to get the next state, which becomes the new current state.

Once the entire string has been processed, the state in which the automation enters is examined.If it is an accept state, the input string is accepted; otherwise, the string is rejected.

Formal Definition

A deterministic finite automaton is defined by a quintuple (5-tuple): A = (Q, ∑, 𝛿, q_o, F).
Where,
Q = Finite set of states,
∑= Finite set of input symbols,
𝛿= A transition function that maps Q X ∑ → Q
q_o: A start state; qo∈Q
F= Set of final states; F ⊆ Q.

A transition function 6 that takes as arguments a state, and an input symbol, and returns a state. In our diagram,  is represented by arcs between states and the labels on the arcs.

If s is a state and a is an input symbol then 𝛿(p,a) is that state q such that there are arcs labeled ‘a’ from p to q.

General Notations of DFA:

There are two preferred notations for describing automata.

• Transition Diagrams
• Transition Tables

Transition Diagrams

A transition diagram for a DFA A = (Q, ∑, 𝛿, q_o, F). is a graph defined as follows:

• For each state is a node represented by a circle.

(q is State)

• A start state is represented by a circle with a preceding arrow labeled at the start.

• Final state is marked by a double circle

(q is Final State)

• For each state q in Q and each input a in Z, if 𝛿(q, a) = p then there is an arc from node q to p labeled a in the transition diagram. If more than one input symbol causes the transition from state q to top then the arc from q to p is labeled by a list of those symbols.

𝛿(q,a)=p

For Example:

Specify a DFA that accepts all and only the strings of 0’s and l’s that have sequence 01 somewhere in the string.
L = {x01y I x and y are any strings of 0’s and l’s}

Fig: The transition diagram for the DFA accepting all strings with a substring 01

Transition Table

A transition table is a conventional, tabular representation of a function 𝛿 that takes two arguments and returns a value. The rows of the table correspond to the states and the columns correspond to the inputs. The entry for the row corresponding to state q and the column corresponding to input a is the state 𝛿( q, a).
The start state is marked with an arrow and the accepting states are marked with a star.

Fig: Transition table for DFA accepting all strings with a substring OI

Extending the Transition Function to Strings:

If 𝛿 is the transition function, then the extended transition function is constructed from 𝛿, called as 𝛿. The extended transition function is a function that takes a state q and a string w and returns a state p. The state that the automaton reaches when starting in state q and processing the sequences of input w.

Language of DFA:

The language of DFA, A = (Q, ∑, 𝛿, qo, F) denoted by L(A) and defined by:

i.e. the language of a DFA is the set of all strings w that takes DFA starting from the start state to one of the accepting states. The language of DFA is called regular language.