TOC[BCS503]Module-1 Notes

MODULE-1
INTRODUCTION TO AUTOMATA THEORY
Automata theory is the study of abstract computing devices or “machines”. Before there were
computersinthe1930’s,Allan Turing studied an abstract machine that had all the capabilities
of today’s computers at least as far as in what they could compute Turing’s goal was to
describe precisely the boundary between what a computing machine could do and what it
could not do; his conclusions apply not only to his abstract Turing machines but to today’s
real machines.

Why Study Automata Theory?

There are several reasons why the study of automata and complexity is an important part of
the core of Computer Science.
Finite automata are a useful model for many important kinds of hard ware and Software.

1. Software for designing and checking the behavior of digital circuits.

2. The “lexical analyzer” of a typical compiler, that is, the compiler component that
breaks the input text into logical units, such as identifiers, keywords and punctuation.
3. Software for scanning large bodies of text, such as collections of Web Pages, to find
occurrences of words, phrases or other patterns.
4. Software for verifying systems of all types that have a finite number of distinct states,
such as communications protocols or protocols for secure exchange of information.

Example: Perhaps the simplest nontrivial finite automaton is an on/off Switch. The device
remembers whether it is in the “on” state or the “off” state, and it allows the user to press a
button whose effect is different, depending on the state of the switch_That is, if the switch is
in the on state, then pressing the button changes it to the on state, and if the switch is in the on
state, then pressing the same button turns it to the on state.

Figure1.1Afiniteautomatonmodellinganon/off switch

[Link] CSE, GCE 2024-25 1

TOC[BCS503]Module-1 Notes

The Central Concepts of Automata Theory

Let us know the most important definitions of terms that pervade the theory of automata.
These concepts include the “alphabet” (a set of symbols), “strings” (a list of symbols from an
alphabet) and “language” (a set of strings from the same alphabet).

i) Alphabets:
Analphabet is a finite, non empty set of symbols. Conventionally, we use the symbol ∑ for an
alphabet.
Common alphabets include:
1. ∑= {0, 1} the binary alphabet.
2. ∑= {a,b, ….,z},the set of all lower-case letters.
3. The set of all ASCII characters, or the set of all printable ASCII characters.

ii) Strings:
A string (or some times word) is a finite sequence of symbols chosen from some alphabet.
For example,01101 is a string from the binary alphabet ∑={0,1}.The string 111 is another
string chosen from this alphabet.

iii) The Empty String

The empty string is the string with zero occurrences of symbols. This string, denoted ε, is a
string that may be chosen from any alphabet what so ever.

iv)Length of a String
Length of a string is the number of positions for symbols in the [Link] has length 5.
The standard notation for the length of a string w is |w|. For example, |011|=3 and |ε| =0.

v) Powers of an Alphabet
If ∑ is an Alphabet we can express the set of all strings of a certain length from that alphabet
by using an exponential notation We define ∑ k to be the set of strings of length k each of
whose symbols is in ∑.

Example: Note ∑0= {ε},regardless of what alphabet ∑ is.

That is, ε is the only string whose length is 0.

[Link] CSE, GCE 2024-25 2

TOC[BCS503]Module-1 Notes

If ∑= {0,1},then
∑1= {0,1},
∑2= {00,01,10,11}
∑3= {000,001,010,011,100,101,110,111} and so on.

The set of all strings over an alphabet ∑ is conventionally denoted ∑*.

For instance, {0, 1}* ={ ε, 0,1,00,01,10,11,000,….............}
∑*=∑0U∑1U∑2U………………..

Sometimes, we wish to exclude the empty string from the set of strings. The set of non empty
strings from alphabet ∑ is denoted ∑+. Thus, two appropriate equivalences are:
∑+=∑0U∑1U∑2U………………..
∑*=∑0U{ε}

vi)Concatenation of Strings
Let x and y be [Link] xy denotes the concatenation of x and y,that is, the string formed
by making a copy of x and following it by a copy of y. More precisely, if x is the string
composed of symbols x=a1a2…..ai and y is the string composed of j symbols y=b1b2bj,
Then xy is the string of length i+j: xy=a1a2…..ai,b1b2bj.

vii)Languages
A set of strings all of which are chosen from some ∑ *, where ∑ is a particular Alphabet, is
called a language. If ∑ is an alphabet, and L then L is a language over ∑.
Examples:

1. The language of all strings consisting of n 0’s followed by n 1’s,for some

n≥0:
{ε, 01, 0011, 000111,……}
2. The set of strings of 0’sand 1’s with an equal number of each:
{ε, 01, 10, 0011, 0101, 1001,.......}
3. The set of binary numbers whose value is a prime:
{10, 11, 101, 111, 1011, …}
4. ∑* is a language for any alphabet ∑.

[Link] CSE, GCE 2024-25 3

 TOC[BCS503]Module-1 Notes

5. Φ, the empty language, is a language over any alphabet.

6. {ε},the language consisting of only the empty string, is also a language over any
alphabet. Note that Φ ≠ {ε}; the former has no strings and the latter has one string.

FINITEAUTOMATA
A finite automaton is a mathematical model which is used to study the abstract machines or
abstract computing devices with inputs chosen from ∑, where ∑ stands for set of alphabets
using which any string can be obtained. On reading the string, the machine may accept or
reject the string.

There mainly 3 different types of FA,

1. Deterministic Finite Automata
2. Non-deterministic Finite Automata
3. Non-deterministic finite automata with ε-moves(ε-NFA)

1. Deterministic Finite Automata (DFA):

Theterm‘deterministic’referstothefactthatoneachinputthereisoneandonlyonestate to which the
automaton can transition from its current state.
Definition of a Deterministic Finite Automaton (2M):
A deterministic finite is defined by a quintuple as, A= (Q,∑,δ,q0,F) where,

[Link] CSE, GCE 2024-25 4

TOC[BCS503]Module-1 Notes

 Q is a finite set of states.

 ∑ is a finite non-empty set of symbols called input alphabet
 δ is a transition function that takes arguments a state and an input symbol and
returns a state.
If q is a state, and a is an input symbol, then δ(q,a) is that state p such that there
is an arc labelled a from q to p.
δ:Q X∑Q
 q0 is the start state, one of the states in Q ic q0∈Q
 F is a set of final or accepting states. The set F is a subset of Q.

How a DFA Processes Strings: Initially the DFA is in state q0. The DFA reads the input
string from left to right one symbol at a time. The changes to state of DFA is dictated by δ.
When the last symbol of input string is read, if this results in the DFA reaching any of its
final state, we say that the string is accepted by DFA, otherwise the string is rejected.

Simpler Notations for DFA’s: There are two preferred notations for describing automata.
a) A transition diagram, which is a graph.
b) A transition table, which is a tabular listing of the function δ which by
implication tells us the set of states and the input alphabet.

a) Transition Diagrams: A transition diagram for a DFA A=(Q,∑,δ,q0,F) is

a graph defined as follows:
 For each state in Q there is a node
 For each state q in Q and each input symbol a in∑, let δ(q,a)=p. Then the
transition diagram has an arc from node q to node p, labelled a. If there are several
input symbols that cause transitions from q to p,then the transition diagram can
have one arc, labeled by the list of these symbols.
 There is an arrow in to the start state q 0 labeled Start. This arrow does not
originate at any node.
 Nodes corresponding to accepting states(those in F)are marked by a double circle.
States not in F have a single circle.
Ex: If A=(Q,∑,δ,q0,F)defined as A=({qo,q1,q2},{0,1},δ,q0,{q1})
where δ={ δ(qo,0)=q2,

[Link] CSE, GCE 2024-25 5

TOC[BCS503]Module-1 Notes

δ(qo,1)=q0,
δ(q1,0)=q1,
δ(q1,1)=q1,
δ(q2,0)=q2,
δ(q2,1)=q1}
The transition diagram is,

Transition Tables:
A transition table is a conventional, tabular representation of a function like δ 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 transition table for the above
example is:

Extended Transition Function:

We define an extended transition function that describes what happens when we start in any
state and follow any sequence of inputs. If δ is our transition function, then the extended
transition function constructed from δ will be called .

“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 sequence of inputs w”.
We define by induction on the length of the input string, as follows:

[Link] CSE, GCE 2024-25 6

TOC[BCS503]Module-1 Notes

Therefore DFA A= ({q0, q1,q2,q3},{0,1}, δ, q0,{q0}} where δ is described by the transition

diagram as shown above.

Suppose the input is [Link] this string has even numbers of 0’sand1’s both, we expect
it is in the language. Thus, we expect that (q0,110101)=q0 since q0 is the only accepting
state.

[Link] CSE, GCE 2024-25 7

TOC[BCS503]Module-1 Notes

The Language of a DFA:

2. Non deterministic Finite Automata (NFA):

A “nondeterministic finite automaton” (NFA) has the power to be in several states at once.
This ability is often expressed as an ability to “guess” something about its input.
Like the DFA, an NFA has a finite set of states, a finite set of input symbols, one start state
and a set of accepting states. It also has a transition function, which we shall commonly call
δ. The difference between the DFA and the NFA is in the type of δ. For the NFA δ is a
function that takes a state and input symbol as arguments but returns a set of zero, one, or
more states, rather than returning exactly one state as the DFA must.

Ex: Let us design a NFA to accept all and only the strings of 0’s and 1’s that end in 01.
Here the possible strings are, L={01, 101, 001, 11101,101001,..}

[Link] CSE, GCE 2024-25 8

TOC[BCS503]Module-1 Notes

Here the NFA has the option of going either to q0 or to q1and infact it does both, as we shall
see when we make the definitions precise. In state q1 the NFA checks that the next symbol is
1 and if so, it goes to state q2 and accepts. Notice that there is no arc out of q1 labeled 0, and
there are no arcs at all out of q2.
Definition of Nondeterministic Finite Automata:

An NFA is represented as a quintuple,

δ:Q X∑ 2Q

The transition table for given NFA can be represented as,

[Link] CSE, GCE 2024-25 9

TOC[BCS503]Module-1 Notes

The Extended Transition Function for NFA

As for DFA’s, we need to extend the transition function δ of an NFA to a function that

takes a state q and a string of input symbols w, and returns the set of states that the NFA is in
if it starts in state q and processes the string w.
Example: Let us trace the input 00101 by the NFA to accept strings ending with 01.

Since we reached the end of the string and automata is in states {qo, q2} where q2 is the final
state, the given string is accepted.
The Language of an NFA:
An NFA accepts a string w if it is possible to make any sequence of choices of next state, while
reading the characters of w, and go from the start state to any accepting state.
Formally, if A=(Q,∑,δ,q0,F),then,

[Link] CSE, GCE 2024-25 10

TOC[BCS503]Module-1 Notes

Equivalence of Deterministic and Nondeterministic Finite Automata

 Although there are many languages for which an NFA is easier to construct
than a DFA, it is a surprising fact that every language that can be described by some
NFA can also be described by some DFA.
 More over, the DFA in practice has about as many states as the NFA, although it often
has more transitions. In the worst case, however, the smallest DFA can have 2 nstates
while the smallest NFA for the same language has only n states.


The proof that DFA’s can do whatever NFA’s can do involves an important

“construction” called the subset construction because it involves constructing all

subsets of the set of states of the NFA. In general, many proofs about automata
involve constructing one automaton from another.

Example:
Let us convert the following NFA to DFA using subset construction method.

[Link] CSE, GCE 2024-25 11

TOC[BCS503]Module-1 Notes

Given NFA,

Since N’s set of states is {q0,q1,q2} the subset construction produces a DFA with 2 3=8states,
corresponding to all the subsets of these three states. Following figure shows the transition
table for these eight states.

The DFA constructed from the NFA is,

3. Finite Automata with Epsilon-Transitions:

An NFA that is allowed to make a transition spontaneously, without receiving an input symbol
is called ε-NFA.
Ex: Let us design a ε-NFA that accepts decimal numbers consisting of:
1. An optional +or– sign
2. A string of digits
3. A decimal point and
4. Another string of digits. Either this string of digits or the string (2) can be empty, but
both cannot be empty at the same time.

Figure: An ε-NFA accepting decimal numbers.

[Link] CSE, GCE 2024-25 12
TOC[BCS503]Module-1 Notes

The Formal Notation for an ε-NFA:

An ε-NFA may be represented exactly as we do an NFA with one exception: the transition
function must include information about transition on ε.
Definition :Formally ε-NFA is defined by,
A= (Q,∑,δ,q0,F)
 Q is a finite set of states.
 ∑ is a finite non-empty set of symbols called input alphabet
 δ is a transition function that takes arguments a state and an input symbol or the
symbol ε and returns zero or one or more states.
δ: Q X∑U{ε }2Q

 q0 is the start state, one of the states in Qicq0∈Q

 F is a set of final or accepting states. The set F is a subset of Q.

Epsilon-Closures:

The ε-closure of any state q denoted by ECLOSE (q) is the set of all states which are reachable
from q on ε transitions only. Formally ε-closure ECLOSE (q) recursively, as follows:

Example:
ECLOSE(2)={2,3,6}
ECLOSE(3)={3,6}
ECLOSE(4)={4}
ECLOSE(5)={5,7}

[Link] CSE, GCE 2024-25 13

TOC[BCS503]Module-1 Notes

[Link] CSE, GCE 2024-25 14

TOC[BCS503]Module-1 Notes

Extended Transitions and Languages for ε-NFA’s:

[Link] CSE, GCE 2024-25 15

TOC[BCS503]Module-1 Notes

Language of an ε-NFA E=(Q,∑,δ,qo,F)is defined as follows:

Eliminating ε-transitions: Converting ϵ-NFA to DFA

[Link] CSE, GCE 2024-25 16

TOC[BCS503]Module-1 Notes

Ans:
Let us find ECLOSE of all the states of given NFA,
ECLOSE(p)={p, q, r}
ECLOSE(q)={q}
ECLOSE(r)={r}
Step1: Since p is the start state of the given NFA, start state of DFA is,
ECLOSE(p)={p,q,r}
Step2:Find transition function of the DFA as follows(use subset-construction method) :

The transition diagram of the DFA is,

An Application of Finite Automata: Text Search

1. Finding Strings in Text:
A common problem in the age of the Web and other online text repositories is the following:
Given a set of words, and all documents that contain one (or all) of those words. A search
engine is a popular example of this process.

The search engine uses a particular technology, called inverted indexes, where for each word
appearing on the Web (there are 100,000,000 different words), a list of all the places where
that word occurs is stored. Machines with very large amounts of main memory keep the most
common of these lists available, allowing many people to search for documents at once.

[Link] CSE, GCE 2024-25 17

TOC[BCS503]Module-1 Notes

Inverted-index techniques do not make use of finite automata, but they also take very large
amounts of time for crawlers to copy the Web and set up the indexes. There are a number of
related applications that are unsuited for inverted indexes, but are good applications for
[Link] that
use automata are:

1. The repository on which the search is conducted is rapidly changing. For example:
(a) Everyday, news analysts want to search the day’s online news articles for relevant
topics. For example, a financial analyst might search for certain stock ticker
symbols or names of companies.
(b) A “shopping robot” wants to search for the current prices charged for the items
that its clients request. The robot will retrieve current catalog pages from the Web
and then search those pages for words that suggest a price for a particular item.

2. The documents to be searched cannot be catalogued. For example, [Link] does

not make it easy for crawlers to find all the pages for all the books that the company
sells. Rather, these pages are generated “on the fly” in response to queries. However,
we could send a query for books on a certain topic, say “finite automata” and then
search the pages retrieved for certain words, e.g., “excellent” in a review portion.

2. Non deterministic Finite Automata for Text Search:

Suppose we are given a set of words, which we shall call the keywords, and we want to find
occurrences of any of these words. In applications such as these. A useful way to proceed is
to design a non deterministic finite automaton, which signals, by entering an accepting state,
that it has seen one of the keywords.
The text of a document is fed, one character at a time to this NFA, which then recognizes
occurrences of the keywords in this text. There is a simple form to an NFA that recognizes a
set of keywords.

[Link] CSE, GCE 2024-25 18

TOC[BCS503]Module-1 Notes

1. A DFA to Recognize a Set of Keywords:

The rules for constructing the set of DFA states is as follows:

[Link] CSE, GCE 2024-25 19

TOC[BCS503]Module-1 Notes

Example:Convert the given NFA to DFA

Note: For exercises/problems under this module-refer class work.

[Link] CSE, GCE 2024-25 20

TOC[BCS503]Module-1 Notes

[Link] CSE, GCE 2024-25 21

TOC[BCS503]Module-1 Notes

[Link] CSE, GCE 2024-25 22

TOC[BCS503]Module-1 Notes

TheDFAtosearchkeywordswebandebayis:

[Link] CSE, GCE 2024-25 23

TOC[BCS503]Module-1 Notes

[Link] CSE, GCE 2024-25 24