Syllabus (COMPUTER APPLICATION)

Course Type: MAJ-16

Semester: 8

Course Code: BBCAMAJ16T

Course Title: Formal Language and Automata Theory

(L-P-Tu): 4-0-0

Credit: 4

Practical/Theory: Theory

Course Objective: Course Objectives: Understand basic properties of formal languages and formal grammars. Understand basic properties of deterministic and nondeterministic finite automata Understand the relation between types of languages and types of finite automata Understanding the Context free languages and grammers, and also Normalising CFG. Understanding the minimization of deterministic and nondeterministic finite automata. Understand basic properties of Turing machines and computing with Turing machines. Understand the concept of Pushdown automata and its application. Understand the challenges for Theoretical Computer Science and its contribution to other sciences.

Learning Outcome: Course Outcomes: Developing concepts of automaton. Understanding the various categories of languages and grammars in the Chomsky hierarchy. Understanding deterministic and nondeterministic finite state automata, and variants of Turing machines. Developing programming skill in Python. Developing knowledge in working with lists, dictionaries. Understating use of various scientific libraries in high level programming environment.

Syllabus: Credit: 4 (L 60)

Finite Automata: Definition of a Finite Automaton, Model, Representation, Classification – with respect to output function Mealy and Moore Machines, with respect to State Transition – Deterministic and Non-Deterministic Machine, Examples, conversion algorithms Mealy to Moore and Moore to Mealy, Finite and Infinite state machines, Finite Automaton, Deterministic and Non-Deterministic Finite automaton, Non-Deterministic to equivalent Deterministic Automaton-Optimized and Non-optimized technique ideas and algorithms, Acceptability of String by a Finite Automaton. [L 10]

Regular Expression: Basic Idea and Definition, Regular Expression basic Identities, Arden’s Theorem – Statement (without Proof) and application for reduction of equivalent regular expressions, Regular expression to Finite Automata conversion, State Transition System to Regular Expression conversion algorithm by Arden’s Algebraic Method, FA to Regular Grammar and Regular Grammar to FA conversion algorithms and applications, Pumping Lemma. [L 15]

Formal Languages and Grammar: Introduction to Formal Grammar and Language, Chomsky’s Classification of Grammar – Type-0, Type-1 or Context Sensitive, Type-2 or Context Free and Type-3 or Regular Grammar, Illustration of each of these classes with example, Sentential form, Sentences – Languages or strings, Derivations. [L 10]

Context Free Language: Context Free Grammar, Parsing, Ambiguity; Normal forms: CNF and GNF, Pumping Lemma.Definition and basic idea about Push Down Automaton, Definition and basic idea about Linear Bounded Automata. [L 10]

Turing Machine: Concepts of Turing Machine, Formal Definitions, Classifications – Deterministic and Non-Deterministic Turing Machines, Simple Design of Turing Machines: Odd-even count and concepts of Universal Turing Machines, Difference and Similarities between Turing Machine and a General Purpose Computer, Definition and significance of Halting Problem in Turing Machine. [L 15]

Reading References:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3^rd Edition, Pearson.
2. Micheal Sipser, Introduction to Theory of Computation, 3^rd Edition, Cengage Learning.
3. K L P Misra & N Chandrasekharan, Theory of Computer Science (Automata, Languages & Computation), 3^rd Edition, PHI.
4. Peter Linz, An Introduction to Formal Languages and Automata, 4th Edition, Narosa.