Theory Of Automata

Text Book
▪Introduction to Automata Theory,
Languages and Computation.
▪ Third edition.
Authors:
John E. Hopcroft, Rajeev Motiwani, Jeffrey D. Ullman.
 Reference Material

1. Introduction to Computer Theory, by Daniel I. Cohen,

John Wiley and Sons, Inc., 1991, Second Edition
2. Introduction to Languages and Theory of Computation, by
J. C. Martin, McGraw Hill Book Co., 1997, Second Edition

3
 What does automata mean?

● It is the plural of automaton, and it means

“something that works automatically”

4
What is automata theory
▪ Automata theory is the study of abstract computational
devices
▪ Abstract devices are (simplified) models of real computations
▪ Computations happen everywhere: On your laptop, on your
cell phone, in nature, …
▪ Why do we need abstract models?
 A simple computer
H
TC
SWI

BATTERY

input: switch
output: light bulb
actions: flip switch
states: on, off
 A simple computer
H
TC
SWI

BATTERY start off on

input: switch
output: light bulb bulb is on if and only if
there was an odd number
actions: f for “flip switch” of flips
states: on, off
 A simple computer
1
1 start off off
1

2 2 2 2
BATTERY
1
2
off on
1

inputs: switches 1 and 2

actions: 1 for “flip switch 1” bulb is on if and only if
actions: 2 for “flip switch 2” both switches were flipped
an odd number of times
states: on, off
A design problem
1 4

?
5
BATTERY

Can you design a circuit where the light is on if and only

if all the switches were flipped exactly the same number
of times?
A design problem
▪ Such devices are difficult to reason about, because they can
be designed in an infinite number of ways
▪ By representing them as abstract computational devices, or
automata, we will learn how to answer such questions
 These devices can model many
things

▪ They can describe the operation of any “small computer”, like the
control component of an alarm clock or a microwave
▪ They are also used in lexical analyzers to recognize well formed
expressions in programming languages:

ab1 is a legal name of a variable in C

5u= is not
Different kinds of automata
▪ This was only one example of a computational device, and
there are others
▪ We will look at different devices, and look at the following
questions:
▪ What can a given type of device compute, and what are its
limitations?
▪ Is one type of device more powerful than another?
Some devices we will see
FINITE Devices with a finite amount of memory.
AUTOMATA Used to model “small” computers.

PUSH-DOWN Devices with infinite memory that can be

AUTOMATA accessed in a restricted way.
Used to model parsers, etc.

TURING Devices with infinite memory.

MACHINES Used to model any computer.

TIME-BOUNDE Infinite memory, but bounded running time.

D TURING Used to model any computer program that
MACHINES runs in a “reasonable” amount of time.
Some highlights of the course
▪ Finite automata
▪ We will understand what kinds of things a device with finite
memory can do, and what it cannot do
▪ Introduce simulation: the ability of one device to “imitate” another
device
▪ Introduce non-determinism: the ability of a device to make
arbitrary choices
▪ Push-down automata
▪ These devices are related to grammars, which describe the
structure of programming (and natural) languages
Some highlights of the course

▪ Turing Machines
▪ This is a general model of a computer, capturing anything we
could ever hope to compute
▪ Surprisingly, there are many things that we cannot compute, for
example:

Write a program that, given the code of another

program in C, tells if this program ever outputs
the word “hello”
▪ It seems that you should be able to tell just by looking at the
program, but it is impossible to do!
Some highlights of the course

▪ Time-bounded Turing Machines

▪ Many problems are possible to solve on a computer in principle,
but take too much time in practice
▪ Traveling salesman: Given a list of cities, find the shortest way to
visit them and come back home
Beijing

Xian
Chengdu Shanghai
Guangzhou
Hong Kong

▪ Easy in principle: Try the cities in every possible order

▪ Hard in practice: For 100 cities, this would take 100+ years even
on the fastest computer!
Preliminaries of automata theory

▪ How do we formalize the question

Can device A solve problem B?

▪ First, we need a formal way of describing the problems that

we are interested in solving
Problems
▪ Examples of problems we will consider
▪ Given a word s, does it contain the subword “fool”?
▪ Given a number n, is it divisible by 7?
▪ Given a pair of words s and t, are they the same?
▪ Given an expression with brackets, e.g. (()()), does every left
bracket match with a subsequent right bracket?
▪ All of these have “yes/no” answers.
▪ There are other types of problems, that ask “Find this” or
“How many of that” but we won’t look at those.
 Fundamentals

(Sets and Theory of Proofs)

Mathematical Preliminaries
Sets
▪ A set is a collection of objects
▪ Order and repetition is irrelevant
▪ X = {1, 2, 3}
▪ X = {n | 1 ≤ n ≤ 3, n ∈ N }
▪ Y = { } = ∅ 🡪 Y is an empty set

▪ The power set of X is the set of all subsets of X

▪ Ρ(X) = 2X = { Y | Y ⊆ X}
▪ |Ρ(X)| = 2|X|
▪ Example X = {1, 2, 3}
▪ 2X = Ρ(X)={{},{1},{2},{3},{1,2},{1,3},{2,3}, {1,2,3}}
▪ {1,2} ⊂ X is a proper subset of X
▪ {1,2,3} ⊂ X is NOT a proper subset of X
▪ {1,2,3} is a superset of {1, 2}
Sets (2)

▪The ∈ symbol signifies membership (belong to):

▪ x ∈ X indicates that x is a member or element of
the set X
▪ x ∉ X indicates that x is not a member or element
of the set X
▪Assume X = {1, 2, 3}, then
▪1 ∈ X, but 4 ∉ X
▪Two sets are equal if they contain the same
members (elements)
▪If X = {1, 2, 3}, Y = {1, 2, 3}, and Z = {2, 3, 4}
▪Then X = Y, but X ≠ Z, and so Y ≠ Z
Sets (3)

▪ Assume X = {1,2,3} and Y = {2,4}

▪ Union
▪ X ∪ Y = {z | z ∈ X or z ∈Y} = {1,2,3,4}

▪ Intersection
▪ X ∩ Y = {z | z ∈ X and z ∈Y} = {2}

▪ Difference
▪ X - Y = {z | z ∈ X and z ∉ Y} = {1,3}
Sets (4)
▪Complement
▪Let X be a subset of Y
▪The complement of X ( X ) with respect to Y is the set
of elements in Y but not in X
▪X = { z | z ∈ Y and z ∉ X } = Y - X
▪Assume X = {1,2,3} is a subset of Y = {1,2,3,4}
▪X = {4}
▪DeMorgan’s Laws

▪(X ∪ Y) = X ∩ Y

▪(X ∩ Y) = X ∪ Y
Proofs
Inductive Proofs

▪Prove a statement S(X) about a family of

objects X (e.g., integers, trees) in three
parts:
▪Basis Step:
▪Prove for one or several small values of
X directly
▪Assumption step :
▪Assume S(Y) for Y smaller than X
▪Prove S(X) using that assumption
Inductive Proofs (EX1)
▪ Prove by induction that
▪ S: 1 + 2 + 3 + ……+ n = n (n + 1) / 2
▪ Basis step:
▪n=1
▪ 1 ( 1 + 1) / 2 = 1
▪ Assumption step:
▪ Assume that S is true for all series of length < n
▪ Prove that S is true for a series of length n?
▪ The series of length n is
▪ 1+2+3+…+n-1+n
▪ By the assumption 1+2+…+n-1 = (n-1)((n-1)+1)/2
▪ Add n to the summation proves S.
Inductive Proofs (EX2)
▪ Example
▪ A complete binary tree with n leaves has 2n - 1 nodes
Inductive Proofs (EX2)

▪ Basis:
▪ If T has 1 leaf, it is a one-node tree. 1 = 2*1 - 1, so OK
▪ Assumption:
▪ Assume that the statement is true for all trees that have leaves
less than n
▪ Proof: Proof that the statement is true for trees that have n leaves
▪ T has two subtrees, U and V
▪ U has u leaves and V has v leaves
▪ According to the assumption: U has (2u – 1) of nodes and V has
(2v – 1) of nodes
▪ T must be a root plus two subtrees U and V. The number of
leaves in T equal number of leaves in U + number of leaves in V
= u+v
▪ The number of nodes in T = (2u – 1) + (2v – 1) + 1 = 2 ( u + v) - 1
▪
If-And-Only-If Proofs

▪Often, a statement we need to prove is of the form

▪“X if and only if Y”
▪We are then required to do two things:
▪Prove the if-part: Assume Y and prove X
▪Prove the only-if-part: Assume X, prove Y
▪Remember:
▪The if and only-if parts are converses of each
other

▪One part, say “if X then Y” says nothing about

whether Y is true when X is false.
▪An equivalent form to “if X then Y” is “if not Y then
not X”; the latter is the contra-positive of the
former.
Equivalence of Sets
▪ Many important facts in language theory are of the form that
two sets of strings, described in two different ways, are really
the same set
▪ To prove sets S and T are the same, prove:
▪ x is in S if and only if x is in T. That is:
▪ Assume x is in S; prove x is in T .
▪ Assume x is in T ; prove x is in S.
Functions
▪Let f be a function defined on a set A and taking
values to a set B. Set A is called the domain of f;
set B is called the range of f.

▪The arity of the functions

▪The number and type of input arguments🡪 the
number and type of output
▪Examples:
▪ The arity of the Multiplication: Num × Num 🡪 Num
▪ The arity of the SquareRoot : Num 🡪 Num