Automata Theory/TCS is the merger of discrete mathematics and abstract computer science. You will learn the mathematical models of computation such as basic machines, deterministic and non-deterministic machines, pushdown and Turing machines.

Learn the rules of the grammars that are used in computer science. Turing Machine will be dealt in greater detail with an emphasis to understand the fundamentals of its working and implementation.

This course is essential to understand the working and building of a compiler. The concepts of undecidable problems will also be made clear.

Batches

No batch is available

What you'll learn?

Introduction

This section will introduce you to the fundamentals of TCS.
 
  • Alphabets, Strings and Languages
  • Chomskey hierarchy and Grammars
  • Finite Automata (FA) and Finite State machine (FSM) 

Regular Grammar

Learn all the rules used in Regular Grammar(RG). Equivalence, conversion to and from a Regular Expression(RE) to Regular Grammar will be discussed.
 
  • Equivalence and Conversion from RE to RG and RG to RE
  • Equivalence of RG and FA, Converting RG to FA and FA to RG
  • Equivalence of RE and FA, Converting RE to FA and FA to RE

Finite Automata

A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set. You will also learn the various types of Finite Automata, Reductions and Equivalence between them.
 
  • Deterministic and Nondeterministic Finite Automata (DFA and NFA)
  • Eliminating epsilon-transitions from NFA
  • FSM with output: Moore and Mealy machines

Regular Language

Regular Language is essentially, the language that can be identified by a Finite Automata. Learn about Pumping Lemma, Closure properties and Myhill-Nerode Thereom in this section.
 
  • Decision properties: Emptiness, Finiteness and Membership
  • Pumping lemma for regular languages and its applications
  • Closure properties
  • Myhill-Nerode Theorem and An application: Text Search

Context Free Grammars

A context-free grammar (CFG) is a set of production rules used to generate patterns of strings. You will study the Normal forms of CFG- CNF and GNF, Pumping Lemma for CFLs (Context Free Languages) and its Closure properties.
 
  • Sentential forms, Leftmost and Rightmost derivations
  • Context Free languages (CFL): Parsing and Ambiguity
  • CFLs: Simplification and Applications
  • Closure properties and Kleene’s closure

Pushdown Automata

Pushdown Automata (PDA) is an automata that uses stack for its operation. Learn the definition of PDA, its language and Deteministic PDA (DPDA) and Multi-Stack DPDA.
 
  • Graphical Notation and Instantaneous Descriptions
  • Language of PDA, Pushdown Stack Machine ( PSM ) as a machine with stack, Start and Final state of PSM
  • PDA/PSM as generator, decider and acceptor of CFG
  • Deterministic PDA (DPDA) and Multi-stack DPDA

Turing Machine

Turing Machine (TM) is used to manipulate the symbols in the input tape on the basis of a mathematical model. This section will cover the design, variants of TM, the power and limitations of TM.
 
  • Design of TM as generator, decider and acceptor
  • Variants of TM: Multitrack, Multitape and Universal TM
  • Equivalence of Single and Multi Tape TMs
  • Power and Limitations of TMs
  • Design of Single and Multi Tape TMs as a computer of simple functions: Unary, Binary (Logical and Arithmetic), String operations (Length, Concat, Match, Substring Check, etc)

Undecidability and Recursively Enumerable Languages

The Undecidable problems requires a yes/no as an answer, but no computer program would always give the correct answer, this leads to interesting outcomes and scenarios. From this section, you will learn the properties of Recursive Languages and the problems related to Decidability and Undecidability.
 
  • Recursive and Recursively Enumerable Languages
  • Properties of Recursive and Recursively Enumerable Languages
  • Decidability and Undecidability, Halting Problem, Rice’s Theorem, Grebach’s Theorem, Post Correspondence Problem
  • Context Sensitivity and Linear Bound Automata

Comparison and scope of languages and machines

This section will compare the relation between languages such as Regular Language (RL),  Context Free Language (CFL) and Context Sensitive Language. Also, the relation between machines such as Finite State Machine (FSM), Pushdown State Machine (PSM) and Turing Machine (TM) will be studied.
 
  • Subset and Superset relation between FSM, PSM and TM
  • Subset and Superset relation between RL, CFL and Context Sensitive Language