Department of Computer and Science Engineering (CSE)
UNIVERSITY INSTITUTE OF
ENGINEERING
COMPUTER SCIENCE
ENGINEERING
Bachelor of Engineering
Theory of Computation (CST-353)
Topic: Introduction DISCOVER . LEARN .
University Institute of Engineering (UIE) EMPOWER
Department of Computer and Science Engineering (CSE)
Learning Objectives & Outcomes
Objective:
• To understand the basics to automata.
Outcome:
• Student will understand the
Basics of automata
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
What is Automata Theory?
• Study of abstract computing devices, or
“machines”
• Automaton = an abstract computing device
• A fundamental question in computer science:
– Find out what different models of machines can do and
cannot do
– The theory of computation
• Computability vs. Complexity
3
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
(A pioneer of automata theory)
Alan Turing (1912-1954)
• Father of Modern Computer
Science
• English mathematician
• Studied abstract machines called
Turing machines even before
computers existed
• Heard of the Turing test?
4
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Theory of Computation: A Historical Perspective
1930s • Alan Turing studies Turing machines
• Decidability
• Halting problem
1940-1950s • “Finite automata” machines studied
• Noam Chomsky proposes the
“Chomsky Hierarchy” for formal
languages
1969 Cook introduces “intractable” problems
or “NP-Hard” problems
1970- Modern computer science: compilers,
computational & complexity theory evolve
5
University Institute of Engineering (UIE)
Languages & Grammars
• Languages: “A language is a
Or “words” collection of sentences of finite
length all constructed from a
finite alphabet of symbols”
• Grammars: “A grammar can
be regarded as a device that
enumerates the sentences of a
language” - nothing more,
nothing less
• N. Chomsky, Information and
Control, Vol 2, 1959
Image source: Nowak et al. Nature, vol 417, 2002
University Institute of Engineering (UIE) 6
The Chomsky Hierachy
• A containment hierarchy of classes of formal languages
Regular Context-
(DFA) Context- Recursively-
free
sensitive enumerable
(PDA)
(LBA) (TM)
University Institute of Engineering (UIE) 7
Finite Automata
1. Finite automata are used to recognize patterns.
2. It takes the string of symbol as input and changes its
state accordingly. When the desired symbol is found,
then the transition occurs.
3. At the time of transition, the automata can either move
to the next state or stay in the same state.
4. Finite automata have two states, Accept
state or Reject state. When the input string is
processed successfully, and the automata reached
its final state, then it will accept.
University Institute of Engineering (UIE) 8
Department of Computer and Science Engineering (CSE)
Finite Automata : Examples
• On/Off switch action
state
• Modeling recognition of the word “then”
Start state Transition Intermediate Final state
state
9
University Institute of Engineering (UIE)
Formal Definition of FA
A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F),
where:
Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function
University Institute of Engineering (UIE) 10
Finite Automata Model:
Finite automata can be represented by input tape and finite
control.
Input tape: It is a linear tape having some number of cells.
Each input symbol is placed in each cell.
Finite control: The finite control decides the next state on
receiving particular input from input tape. The tape reader
reads the cells one by one from left to right, and at a time only
one input symbol is read.
University Institute of Engineering (UIE) 11
University Institute of Engineering (UIE) 12
Types of Automata:
There are two types of finite automata:
DFA(deterministic finite automata)
NFA(non-deterministic finite automata)
University Institute of Engineering (UIE) 13
Some important points about DFA and NFA:
Every DFA is NFA, but NFA is not DFA.
There can be multiple final states in both NFA and DFA.
DFA is used in Lexical Analysis in Compiler.
NFA is more of a theoretical concept.
University Institute of Engineering (UIE) 14
Department of Computer and Science Engineering (CSE)
Alphabet
An alphabet is a finite, non-empty set of symbols
• We use the symbol ∑ (sigma) to denote an
alphabet
• Examples:
– Binary: ∑ = {0,1}
– All lower case letters: ∑ = {a,b,c,..z}
– Alphanumeric: ∑ = {a-z, A-Z, 0-9}
– DNA molecule letters: ∑ = {a,c,g,t}
– …
15
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Powers of an alphabet
Let ∑ be an alphabet.
– ∑k = the set of all strings of length k
– ∑* = ∑0 U ∑1 U ∑2 U …
– ∑+ = ∑1 U ∑2 U ∑3 U …
16
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Strings
A string or word is a finite sequence of symbols
chosen from ∑
• Empty string is (or “epsilon”)
• Length of a string w, denoted by “|w|”, is equal to
the number of (non- ) characters in the string
– E.g., x = 010100 |x| = 6
– x = 01 0 1 00 |x| = ?
– xy = concatentation of two strings x and y
17
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Summary
• Automata theory & a historical perspective
• Chomsky hierarchy
• Finite automata
18
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
FAQ :
1. What are types of finite automata.
2. Explain model of finite automata.
3. Explain tuples of finite automata.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
References :
• Martin J.C., “Introduction to Languages and Theory of
Computation”, Tata McGraw-Hill Publising Company
Limited, 3rd Edition.
• https://youtu.be/S3cOulqSAmU
• Https://en.wikipedia.org/wiki/Finite-state_machine
• https://www.safaribooksonline.com
• https://nptel.ac.in/courses/106/103/106103070/
University Institute of Engineering (UIE)
THANK YOU
University Institute of Engineering (UIE)
