INTRODUCTION TO AUTOMATA

THEORY AND LANGUAGES

NMCA-214

Zero Lecture
Mrs. Anamika Maurya
Assistant Professor
MCA, PSIT

Subject Overview

Theory Subject
No practical session
100 marks
4 credit
6 lectures in week
Total 60 lectures

13/01/2016

Books

Authors

Publisher

Introduction to Automata
Theory, Languages and
Computation

John E. Hopcroft, D.
Ullman

Pearson Education,
3rd Ed.

An Introduction to Formal
languages and automata

Peter Linz

Narosa, 2012, 4th Ed

Theory of Computer
Science

K. L. P. Mishra

Prentice-Hall, 2007,
3rd Ed.

Formal Languages
and Automata Theory

C. K. Nagpal

Oxford Higher
Education, 2013

13/01/2016

Automata Theory
Plural of automaton, means to automate
or mechanize
An automaton is a machine that can
perform computation in a mechanized
manner
Basic aim of studying automata theory is,
what is computable and what is not
Study of abstract machine that can
perform computing
13/01/2016

Introduction
Computer machine understands the
instruction given by human unambiguously
Develop languages for writing instructions
For a computer science student, it is
necessary to study
Computability ( to know what is computable)
Formal Languages ( to design languages to
write instructions for machine)
Automata theory (design computing machine)

13/01/2016

Why we study Automata Theory

There are several reasons to study of
automata and complexity is an
important part of the core of
computer science.
1. Introduction to Finite Automata
2. Structural Representation
3. Automata and Complexity
13/01/2016

Introduction to Finite Automata

Software for designing and checking the
behaviour of digital circuits
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.
13/01/2016

Introduction to Finite Automata

Software for scanning large bodies of text,
such as collections of Web pages, to find
occurrences of words, phrases, or other
patterns.
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.

13/01/2016

Structural Representations:
There are two important notations there
are not automation-like, but play an
important role in the study of automata
and their applications
Grammars are useful models when
software that processes data with a
recursive structure.
Regular Expressions are denoted the
structure of data, especially text strings.
13/01/2016

Automata and Complexity

Automata are essential for the study of the limits of
computation.
There are two important issues.
1. What can a computer do at all? This study is
called decidability, and the problems that can
be solved by computer are called decidable..

13/01/2016

10

Practical application of
Automata Theory
You want to spot duplicate
occurrences of a phrase in a
document and delete the second
occurrence. In essence, you want to
substitute a sequence in a
language.
Does a program contain an
assertion violation?
13/01/2016

11

Practical application of
Automata Theory
Does a device driver respect certain
protocols when interacting with the
kernel? The behaviour of a program is
a set of executions; in other words, a
language. The correctness property is
another language. The program
correctness problem amounts to a
language inclusion check.
13/01/2016

12

Practical application of
Automata Theory

What can a computer do efficiently? This

study is called intractability, and the problems
that can be solved by a computer using no
more time than some slowly growing function
of the size of the input are called tractable.
Often, we all polynomial functions to be slowly
growing, while functions that grows faster
than any polynomial are deemed to grow too
fast.

13/01/2016

13

Automata theory and formal

languages are the base of

Current compilers,
Regular expressions,
Parsers,
Web-scrappers,
Natural language processing
(NLP),
State machines based on markov
chains
13/01/2016

14

13/01/2016

15

13/01/2016

16

Example of Machine
A table is an information processing
machine with the i/p signals being either
up or down position of switch and o/p
signals being either on or off.
An adder is an information processing
machine with the input signals being to
decimal number and output signal being
their sum.
13/01/2016

17

Example of Machine
An automobile is an information
processing machine with depression of
accelerator and angular position of
steering wheel is an input signal and
output signal are speed and direction

13/01/2016

18

Syllabus
UNIT 1:Basic concepts of Automata
Theory
UNIT 2: Regular Expressions and
Languages
UNIT 3: Non-Regular Grammars
UNIT 4: Turing Machines
UNIT 5: Undecidability
13/01/2016

19

Unit 1
Alphabets, Strings and Languages,
Deterministic Finite Automata (DFA)
Nondeterministic Finite Automata
(NFA),
Language of DFA and NFA.
NFA with -transitions,
Language ofNFA with -transitions
Equivalence of NFA and DFA.
13/01/2016

20

Unit 2
Regular Expressions and Languages: Introduction,
Definition of regular expression,
KleensTheorem,
Equivalence of regular expression and Finite
Automata,
Pumping Lemma for regular
Languages, Closure properties of Regular
Languages,
Decision properties of Regular Languages,
Finite Automata with Output: Moore and Mealy
Machine,
Equivalence of Moore and Mealy Machines.
13/01/2016

21

Unit 3
Non-Regular Grammars: Definition of Grammar,
Classification of Grammars,
Chomosky's Hierarchy.
Context Free Grammars (CFG) and Context Free
Languages (CFL)
Derivation trees,
Ambiguous Grammars,
Simplification of Grammars,
Normal forms of CFGs: CNF and GNF,
Closure properties of CFLs,
Decision Properties of CFLs,
Pumping lemma for CFLs. Push Down
Automata (PDA): Definition and Description,
13/01/2016
22
Language of PDA and its applications.

Unit 4
Turing Machines: Introduction,
Basic Features of a Turing Machine,
Language of a Turing Machine,
Variants of Turing Machine:
Multitapes,
Nondeterministic Turing Machine,
Universal Turing Machine.
Turing Machine as Computer of Integer functions,
Halting problem of Turing Machine,
Church-TuringThesis.
13/01/2016

23

Unit 5
Undecidability: Introduction
Undecidable problems about Turing
Machines,
Rice's Theorem,
Post's Correspondence problem (PCP)
Modified PCP
Tractable and Intractable Problems:
P and NP, NPComplete Problems,
Introduction to recursive function theory.
13/01/2016

24

Lecture Plan Timeline

UNIT
1

11 Lecture

UNIT
2

10 Lecture

UNIT
3

UNIT
4

24 Lecture

8 Lecture

UNIT
5

7 Lecture

Outcomes
Student will be able to
Differentiate
between NFA
and DFA
Design Finite
automata

Differentiate
between Mealy
and Moore
Write the regular
expression for
regular languages
Apply Ardens
Theorem and
Pumping Lemma

Write CFG
Design PDA
Understand the
simplification of
CFG
Understand the
Closure and
decision
property of
CFL

13/01/2016

Explain the
Concept
and working
of Turing
Machine
Differentiate
between
variants of
Turing
Machine
Describe the
Halting
Problem of
Turing
Machine

Understand
the concept
of decidability
Define the
concept of P,
NP and NP
complete
problem
Know the
concept of
PCP problem

26

Future scope of Subject

UPTU Exam /Any University Exam

GATE
UGC NET
PSU for CS Student
Base of Compiler Design

13/01/2016

27

Rules
No cell phone
Full duplex
Previous topic
revision

13/01/2016

28

Thank You

13/01/2016

29