UE21CS243A_ Automata Formal Languages and Logic
(4-0-0-4-4)
Semester III
The course introduces fundamental concepts in Automata and Formal Languages and their
application to Logic. The course covers the notions of Finite State Automaton, Regular
expression, Push down Automaton, Context Free Languages and Turing Machines. These
abstract and formal models and their usage in Propositional and First Order Predicate Logic,
allow for solving problems in Formal language Generation and Recognition.
Course Objectives:
Teach students to construct basic machines like DFA, NFA which represent Regular
Languages.
To familiarize students to construct Regular Expressions, Regular Grammars and to
identify Non – Regular Languages.
Teach students to identify Context Free Languages, to construct Push down Automata
which represent Context Free Languages, to convert the given grammar to various normal
forms and to make use of Membership Algorithm.
Teach students to understand closure properties of Context Free Languages, to identify
Non – Context Free Languages and to construct Turing Machines and familiarize students
with concepts like Recursively Enumerable languages, Recursive Languages, Undesirable
Problems.
To familiarize notions of mathematical logic: logical notations (syntax) and how to assign
meaning to them (semantics).
Course Outcomes:
At the end of the course, the student will be able to:
Design simple machines like DFA, NFA, convert NFA to DFA and minimize a given DFA.
Construct regular expressions for different languages, verify that some languages are
regular and some are not.
Analyze the difference between Regular Languages and Context Free Languages, design
Push Down automata, construct Context Free Grammars, and convert one form of the
grammar to another form.
Enumerate the properties of Context Free Grammars, verify that some languages are
context free and some are not, design Turing Machines, and analyze the difference
between acceptability and decidability and Analyze the difference between Recursive and
Recursively Enumerable Languages, Decidable Languages, Turing – Recognizable and
Co – Turing – Recognizable, some problems that cannot be solved by Turing
Machines, reduce one Undesirables Problem to another, Undeniable Problems for
Recursively Enumerable Languages.
Make use of Propositional Logic and Predicate Logic in knowledge representation and
truth verification.
Course Outline:
AFLL is a 4-credit course. The course plan is for 75 hrs designed as follows:
Lecture Hours: 56 hrs
Unit wise revision/case study sessions: 10 hrs
Assignments: 4 Hrs
ISA: 5 Hrs
Course Information
Hours Topic Chapter Coverage
and Section % of Cumulative
Syllabus %
Unit 1: Introduction
1. Mathematical Preliminaries and T1 – 1.1 18 18
Notation, T2 – 1.2
2. Three Basic Concepts. Finite Automata: T1 – 2.1
Deterministic Finite Accepters
3. Deterministic Finite Accepters T1 – 2.1
4. Deterministic Finite Accepters T1 – 2.1
5. Non-Deterministic Finite Accepters, T1 – 2.2
6. Non-Deterministic Finite Accepters, T1 – 2.2
7. Equivalence of Deterministic and Non- T1 – 2.3
Deterministic Finite Accepters,
8. Equivalence of Deterministic and Non- T1 – 2.3
Deterministic Finite Accepters,
9. Reduction of the number of states in T1 – 2.4
Finite Automata.
10. Reduction of the number of states in T1 – 2.4
Finite Automata.
11. Unit wise revision session
12.
13. ISA 1
Unit 2: Regular Languages and Grammars
14. Regular Expressions. T1 – 3.1 18 36
15. Regular Expressions T1 – 3.1
16. Connection between Regular T1 – 3.2
Expressions and Regular Languages.
17. Equivalence of two Regular T1 – 3.2
Expressions,
18. Regular Grammars T1 – 3.3
19. Regular Grammars, Equivalence of T1 – 3.3
Regular Grammar and Finite Automata
20. Equivalence of Regular Grammar and T1 – 3.3
Finite Automata
21. Properties of Regular Languages T1 – 4.1
Elementary Questions about Regular T1 – 4.2
Languages
22. Pumping Lemma T1 – 4.3
23. Pumping Lemma, Identifying Non T1 – 4.3
Regular Languages.
24. Unit wise revision/case study session
25.
26. ISA 2
Unit 3: Pushdown Automata and Context Free Languages
27. Definitions of PDA and CFL, T1 – 7.1 21.3 57.3
Deterministic Pushdown Automata,
28. Deterministic Pushdown Automata, T1 – 7.1
29. Non-Deterministic Pushdown T1 – 7.2
Automata,
30. Non-Deterministic Pushdown T1 – 7.2
Automata,
31. Pushdown Automata and Context Free T1 – 7.2
Languages,
32. Context Free Grammars, T1 – 5.1
33. Context Free Grammars, T1 – 5.1
34. Parsing and Ambiguity. Simplification T1 – 5.2
of Context–Free Grammars.
35. Normal Forms: Methods for T1 – 6.1
Transforming Grammars, Two T1 – 6.2
Important Normal Forms:
Chomsky Normal Form
36. CYK Algorithm T1 – 6.3
37. Greibach Normal Form T1 – 6.2
38. CFG to PDA T1- 7.2
39. Unit wise revision session
40.
41. ISA 3
Unit 4: Properties of Context-Free Languages
42. Properties of Context-Free Languages: T1- 8.2 21.3 78.6
Closure Properties and Questions about
Context–Free Languages,
43. Pumping Lemma for Context–Free T1- 8.1
Languages.
44. Pumping Lemma for Context–Free T1- 8.1
Languages.
45. Turing Machines: The Standard Turing T1- 9.1
Machine, Constructing Turing
Machines,
46. Constructing Turing Machines, T1- 9.1
47. Combining Turing Machines for T1- 9.2
Complicated Tasks,
48. Combining Turing Machines for T1- 9.2
Complicated Tasks, Turing’s Thesis. T1- 9.3
49. Hierarchy of Formal Languages and T1- 11.1
Automata: Recursive and Recursively
Enumerable Languages, the Chomsky
Hierarchy.
50. Limits of Algorithmic Computation: T1- 12.1
Some Problems that cannot be solved by T1- 12.3
Turing Machines
51. Undecidable Problem for Recursively T1- 12.2
Enumerable Languages,
52. Undecidable Problem for Recursively T1- 12.2
Enumerable Languages, idea of T1- 11.3
reduction
53. Unit wise revision session
54.
55. ISA 4
Unit 5: Propositional Logic
56. A very simple Logic, Syntax, Semantics, T2- 7.4, T2- 21.3 100
7.4.1, T2-
7.4.2
57. A simple knowledge Base, A simple T2- 7.4.3, T2-
inference procedure. 7.4.4
58. Propositional Theorem Proving: T2- 7.5.1,
Inference and Proofs, 7.5.2
59. Proof by Resolution T2- 7.5.1,
7.5.2
60. Conjunctive Normal Form T2- 7.5.1,
61. Conjunctive Normal Form T2- 7.5.1
62. A resolution algorithm. T2- 7.5.2
63. Syntax and Semantics of First Order T2- 8.2
Logic:
64. Models for First Order Logic Symbols T2- 8.2
and interpretations,
65. Terms, Atomic Sentences, Complex T2- 8.2
Sentences
66. Quantifiers, Equality, Numbers T2- 8.3.3
67. Sets and Lists. Example - The electronic T2- 8.4.2
circuits’ domain.
68. Problems Based on CNF and Resolution
algorithm
69. ISA 5
70. Unit wise revision session
71. Introduction to Prolog Programming
72. Assignment 2: Syntax Validation of a
73. programming language by writing the
Context Free Grammar.
(PLY, ANTLR Tools)
74. Assignment 1: Implementation of
75. RegEx for NLP Applications
Tools:
JFLAP - Java Formal Languages and Automata Package
Text Book(s):
1. “An Introduction to Formal Languages and Automata”, Peter Linz, Jones and Bartlett,
New Delhi, India, 5th Edition, 2011.
2. Artificial Intelligence – A Modern Approach”, Stuart Russell and Peter Norvig,Pearson,
3rd Edition (Paperback),2016
References:
1. “Theory of Computation”, Michael Sipser, Cengage Learning, New Delhi, India, 2008.
2. “Introduction to Automata Theory, Languages, and Computation”, John E Hopcroft,
Rajeev Motwani, Jeffrey D Ullman, Pearson Education, New Delhi, India, 3rd Edition, 2009.
3. “Theory of Computation: A Problem–Solving Approach”, Kavi Mahesh, Wiley India, New
Delhi, 2012