Theory of Automata & Formal Language
Theory of Automata & Formal Language
Course Information
Institution: Benazir Bhutto Shaheed University Lyari, Karachi, Pakistan
Department: Computer Science
Level: Undergraduate
Prerequisites: Discrete Mathematics
Course Description
The primary objective of this course is to familiarize students with the fundamental concepts of computation within the field of computer science. Students will learn about the connections between formal languages, formal grammar, and automata. The course will offer theoretical and practical knowledge regarding regular languages, finite automata, context-free languages, pushdown automata, recursively enumerable languages, Turing machines, the Universal Turing Machine, decidability, and the halting problem.
Learning Outcomes
Upon successful completion of this course, students will be able to:
- Articulate and manipulate essential concepts in automata theory and formal languages
- Construct formal proofs for deterministic and non-deterministic automata
- Design and analyze regular expressions and regular languages
- Work with context-free grammars and pushdown automata
- Understand the equivalence between deterministic and non-deterministic finite automata
- Analyze the relationship between finite automata and regular expressions
- Comprehend Turing machines and computability theory
Course Outline
| Lecture | Topic |
|---|---|
| 1 | What does automata mean?, Why study automata?, Languages introduction |
| 2 | How to Communicate with machines: Three aspects/specifications of languages, Formal Languages |
| 3 | Formal vs. Informal languages, Finite vs. Infinite Languages, Defining Languages, Some observations |
| 4 | Mathematical Preliminaries: Sets, Disjoint Sets, Powersets, Cartesian Product, Set Cardinality, Set operations, Demorgan’s law |
| 5 | Languages, Operations on Languages, Alphabets and Strings |
| 6 | String Operations, Empty String, Substring, Prefix and Suffix, Star-Closure (Kleene *), Positive Closure, Recursive Language Definition |
| 7 | Regular Expressions |
| 8 | Some Examples of REs |
| 9 | Languages associated with REs, Regular Languages |
| 10 | Some Examples of REs, Equivalent Regular Expressions |
| 11 | Introduction to Finite Automata and Rules for making FSA States |
| 12 | Transition, Acceptance or Rejection of string |
| 13 | Pictorial representation of Finite Automata: Some Practice examples in the class |
| 14 | Nondeterministic finite automata (NFA) |
| 15 | NFAs with epsilon transition, Some more Examples |
| 16 | Transition Graph |
| 17 | Generalized Transition Graph |
| 18 | NFA to DFA Conversion |
| 19 | Kaleen’s Theorem: Proof of part 1,2 |
| 20 | Finite Automata With Output: Moore Machines |
| 21 | Finite Automata With Output: Moore Machines |
| 22 | Finite Automata With Output: Mealy Machines |
| 23 | Finite Automata With Output: Mealy Machines |
| 24 | Conversion from one model to another |
| 25 | Regular Languages and Properties: Closure Properties |
| 26 | Closure Properties of Regular Languages (Union) |
| 27 | Proof with machine: Complement, Intersection, Closure, and Concatenation of a RE |
| 28 | Non regular Languages |
| 29 | Pumping Lemma |
| 30 | Myhill-Nerode Theorem |
| 31 | Context Free Grammars (CFG) and CFL |
| 32 | CFG For identifier, CFG For arithmetic expressions, Backus-Naur Form |