# 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 an input by moving through a series of states. At each state of the computation, a transition function determines the next conﬁguration on the basis of a ﬁnite 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 is the Turing machine.

#### Characteristics of such machines include:

• Inputs: assumed to be sequences of symbols selected from a ﬁnite 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 ﬁnite set Z. Namely, set Z is the set {y1,y2, y3,....,ym} where m is the number of outputs.
• States: ﬁnite set Q, whose deﬁnition depends on the type of automaton.

An automaton has a mechanism to read input, which is string over a given alphabet. This input is actually written on an input tape /file, which can be read by automaton but cannot change it.
Input ﬁle is divided into cells each of which can hold one symbol. Automaton has a control unit which is said to be in one of finite number of internal states. The automation can change states in
a deﬁned 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 ﬁnite-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 which gives all relevant information necessary to determine how the system can evolve from that point on.

Transitions are changes of 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 ﬁnite- 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), 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 which maps an ordered sequence of input events into a corresponding sequence, or set, of output events.

In order to fully understand conceptually a ﬁnite-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 ﬂoor, the direction of motion (up or down) and the collection of not-yet satisﬁed requests for services. Therefore, at any given moment in time, an elevator in operated would be defined by the following mathematical terms:

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

#### Applications of Finite State Machines

• Trafﬁc Lights
• Video Games
• Text Parsing
• CPU Controllers
• Protocol Analysis
• Natural Language Processing
• Speech Recognition

#### Types of Finite Automata:

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

### Deterministic Finite Automata (DFA)

Deterministic Finite State Automata (DFA) are 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 reﬂect 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 ﬁnite number of cells. Each cell holds a symbol from .
• A control , which itself consists of 3 things:
1. ﬁnite number of states that the machine is allowed to be in (zero or more states are designated as accept or ﬁnal 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 symbol s 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 Deﬁnition

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

A transition function 6 that takes as arguments a state, 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, ∑, 𝛿, qo, F). is a graph defined as follow:

• For each state is node represented by circle.
(q is State)

• A start stat is represented by a circle with preceding arrow labeled at 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 cause the transition from state q top then 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 transition function, then the extended transition function 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 deﬁned by:

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