Unit 1

Introduction about Automata

By- JIIT Noida

 Course Outcomes:
S. No. Course Outcomes Level of
Attainment
CO-1 Broaden knowledge of the fundamental mathematical and computational principles that Remember,
are the foundation of computer science Understand
CO-2 Understand the concept of Deterministic Finite Automata and Non-Deterministic Finite
Evaluate
Automata, minimize the states, usage Moore and Mealy Machine
CO-3 Understand how to use the context free grammars and how to derive parse trees and solve
ambiguity problems;
Evaluate
Understand Normal forms for Context Free Grammar’s Chomsky and Greibach Normal
Forms, Push Down Automaton algorithm
Understand the basic concepts of Turing Machine, configuration of Turing Machine,
CO-4 computing, multiple tapes, two-way infinite tape concepts, concept of non-deterministic Apply
Turing machines
CO-5
Understand the computational power of languages, numerical functions applied to Turing
machines, numerical functions applied to Turing machines, concept of halting problem. Evaluate
Grammars, properties of recursive languages, concept of polynomial decidable
 Course Description
Unit Contents Lectures
required
1 General introduction, Complexity theory, Computability theory, Automata theory, Mathematical preliminaries 3
Infinite Sets, Closures, Alphabets, Languages & Representation

2 Finite Automata and Regular Languages, Deterministic finite automata, Regular operations, Non-deterministic 9
finite automata, Equivalence of DFA sand NFAs, Closure under the regular operations

3 Regular expressions, Equivalence of regular expressions and regular languages, The pumping lemma and 5
non-regular languages
4 Context-Free Languages, Context-free grammars, Parse Trees & Ambiguity, Chomsky and Greibach Normal 5
forms
5 Push Down Automata, Equivalence of PDA and CFG, Properties of context free languages, Determinism & 9
Parsing DCFG, Top-down & Bottom-up Parsing

6 Turing Machine-Introduction, Recursive and Recursively Enumerable Language, Multi-tape Turing machines, 5
Non-deterministic Turing machines, Universal Turing machines, Halting problem

7 Decidable and Undecidable Languages; Complexity Theory, The Complexity Class NP, NP Completeness and 6
Reducibility NP complete problems

Total lectures 42
 Reference Material
Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books, Reference
Books, Journals, Reports, Websites etc. in the IEEE format)
Text Books
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013) “Introduction to Automata Theory, Languages, and
1.
Computation” (3rd ed.). Pearson.
2. Raghavan, Compiler Design, TMH Pub,2013
Edition Reference Book(s):
Alfred Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, “Compilers: principles, techniques, and tools,” 2nd
3.
Edition, Pearson Education
4. John C. Martin, “Introduction to Language and the Theory of Computation”, TMH 2004
K. L. P. Mishra, N. Chandrasekaran, “Theory of Computer Science Automata, Languages and Computation”,
5.
3rdEdition, PHI 2007
S.P.Eugene, “Theory of automata, formal language and computation”, New Age International Publishers , New
6.
Delhi 2003
7. Sipser, M., Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, 2007

8. ACM Transactions on Computation Theory 9. ACM Journal on Theory of Computation.

9. D. Kozen, Automata and computability, Springer, 1997.
10. B. Khoussainov, A. Nerode, Automata theory and its applications, Springer, 2001. 4
 Assignments
• Assignments will be posted on Google Classroom.

• Assignments should be submitted on Google Classroom before

deadline.

5
 Project
• After T1, I will give you one mini project to work on.

• It may be
• Some designing
• Study of a research paper

6
 Good thing about this subject

No need to worry about specifics of

programming languages and/or
computing platforms

Design solutions to real world problems

with simplicity

7
 What all is required?

Basic
Mathematical
Rigorous
Background Thinking

Approach
Solution
Simple
Fundamentals
of Discrete Logical
Mathematics Mind

Basics Basic
Knowledge Knowledge
of of Data
Algorithms Structures

8
 Applications
• Web Search • Spell Checker
• Crawler • Ad hoc mobile
• Game Theory networks
• Text Processing • Robotics
• Compiler Design • AI
• Pattern Recognition • Routing
• Operating System • Computational Biology
• Circuit Design

9
 Fundamental Theme

• What are the capabilities and limitations of

computers ?

• What can we do with computers?

• Are there somethings which we cannot do with

computers?

10
Are there things we cannot do with
computers?
The halting problem We allow our computers unbounded memory and
unbounded time to operate. Given a fixed computer C, consider the
following task: decide (maybe, with the help of another computer, C0) for
each possible program p for C, whether when we start computer C on
program p, it will ever finish the computation?
• Solving integer equations Are there algorithmically unsolvable problems
about things other than computers? Yes. Consider an equation of the form
x^3 = 3y^6 −2x^4 −11. We are interested in finding out whether this
equation has any solution in integers. Is there any algorithm to solve all
such problems?
• Post Corespondence problem : Given two lists of words (a1, a2, .., an) and
(b1, b2, .., bn), find a sequence of indices so that the concatenated words
are equal. E.g. given the lists (1: a, 2: ab, 3: bba) and (1: baa, 2: aa, 3: bb),
the sequence (3, 2, 3, 1) is a solution since bba+ab+bba+a =
bb+aa+bb+baa. Is not possible to say whether any such PC solution exits or
not under all circumstances
11
 What else?
• In GATE exam, 20% syllabus is Automata and compiler design.

• Opportunities after Gate exam:

• Higher studies
• Job in PSUs

12
 Why do we need to study automata?

Automata theory is important because it allows scientists to

understand how machines solve problems. An automaton is
any machine that uses a specific, repeatable process to
convert information into different forms. Modern computers
are a common example of an automaton.
 Modern applications of automata theory go far
beyond compiler techniques or hardware
What is the verification. Automata are widely used for modelling
use of and verification of software, distributed systems,
automata? real-time systems, or structured data. They have
been equipped with features to model time and
probabilities as well.
Theory of Automata : definition with real time example

An Automata is used for recognizer called acceptor and as a transducer i.e. a

machine with output capability as well. An acceptor automata accepts a set of
words or strings and rejects others. The main application of automata is in
designing of lexical analyzer, which is an important part of Compiler.
Under the computer science branch the term ‘Automata’ means
‘Discrete Automata’ and it is defined as;
 The characteristics
of automata are
as follow;

Input Output States Output relation

 According to the characteristics of automata, it is useful to run on some
given sequence of inputs in discrete time steps. An automaton gets one
input every time step that is picked up from a finite set of alphabets. At any
time, the symbols so far fed to the automaton as input string. At each time
step when the automaton reads an input string, it jumps or transitions to
another state that is decided by a transaction function that takes the
current state and input symbol as input parameters for the computation of
next state or output. The automaton reads the alphabets of input strings
one after another and transitions from state to state as per the transition
function rules, until the string is read completely by automation machine.
Once the input word has been read, the automaton is said to have stopped
and the state at which automaton has stopped named the final state.
Depending on the final state of the machine, it’s cleared that the
automaton either accepts or rejects an input string.
 Example of Automata

Regular
Sequential Vending Traffic Video Speech
Text Parsing: Expression
machine: Machines: Lights: Games: Recognition:
Matching:
Computation

CPU Memory

20
 Computation

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

21
Example: Compute 5*x

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

y=5*x
22
Example: Compute 5*x

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

y=5*x x =7
23
 Example: Compute 5*x

y=5*7=35

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

y=5*x x =7
24
 Example: Compute 5*x

y=5*7=35 y =35

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

y=5*x x =7
25
 Computation
Automata

Temporary Output
Memory Memory

CPU
Program Input
Memory Memory

26
 Branches of ToC

Branch Concerned With Tool

Modeling machines and
Automata Theory DFA, NFA, PDA, TM
recognizing languages
Computability Theory What can be computed? Recursive functions, TMs
How efficiently can it be
Complexity Theory Time/space complexity
done?
 Different Kinds of Automata

Automata are distinguished by the kind of temporary

memory they use

• Finite Automata: no temporary memory

• Pushdown Automata: stack

• Turing Machines: random access memory

30
 Power of Automata

Finite Pushdown Turing

Automata Automata Machine

Less power More power

Solve more
computational problems
31
Chomsky Hierarchy

32