Zero Lecture

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
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
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

Zero Lecture

Uploaded by

Copyright:

Available Formats

Zero Lecture

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Zero Lecture

Uploaded by

Copyright:

Available Formats

INTRODUCTION TO AUTOMATA

THEORY AND LANGUAGES

Narosa, 2012, 4th Ed

Why we study Automata Theory

Introduction to Finite Automata

Introduction to Finite Automata

Automata and Complexity

What can a computer do efficiently? This

Automata theory and formal

Lecture Plan Timeline

Future scope of Subject

UPTU Exam /Any University Exam

You might also like