Theory of Automata & Formal Language
Course Details
- Course Title: Theory of Automata & Formal Language
- Course Code: CS-351
- Credit Hours: 3
- Pre-requisite: Discrete Mathematics
- Offered To: BS (CS)
- Level: Undergraduate
- Institution: Benazir Bhutto Shaheed University Lyari (BBUSL), Karachi, Pakistan
- Faculty: Faculty of Computer Science & Information Technology
- Semester Offered: Fall 2016
Objectives
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
By completing this course, students will be equipped to articulate and manipulate essential concepts in automata theory and formal languages. This includes formal proofs, deterministic and non-deterministic automata, regular expressions, regular languages, context-free grammars, and Turing machines. Students will grasp the equivalence between deterministic and non-deterministic finite automata and the relationship between finite automata and regular expressions. Furthermore, they will develop a comprehensive understanding of the strengths and limitations inherent in regular and context-free languages.
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 |
Assessment Criteria
Theory
- Quizzes, Assignments, Presentations: 20 Marks
- Mid-term Examination: 30 Marks
- Final Examination: 50 Marks