Theory of Formal Languages and Automata
The theory of languages and automata primarily focuses on two important aspects of the theory of computation: formal languages and automata. A good knowledge of discrete mathematics as well as algorithm design is expected for taking this course. Hence, the sophormeore or junior students in computer sicence/computer engineering are the prospective audiences for this course.
Text Books
1. Peter Linz: An Introduction to Formal Languages and Automata, 4rd Edition, 2010.
2. Thomas A. Sudkamp: An introduction to the theory of computer science languages and machines, 3rd Edition, 2005.
* The PDF format of these books are available at 'Personal' page.
Grading
Final = 85%
Homeworks = 20%
Tentative Schedule
| Date | Syllabus | Readings | Assignments |
|---|---|---|---|
| Sat, 01 - 07 - 91 |
Overview Three basic concepts |
Class Notes Ch 1.2 |
|
| Sun, 02 - 07 - 91 |
Languages Proof by induction |
Ch 1.2 Ch 1.1 |
|
| Sat, 08 - 07 - 91 |
DFA | Ch 2.1 | |
| Sun, 09 - 07 - 91 |
NFA | Ch 2.2 | HW1 | Sol-HW1 |
| Sat, 15 - 07 - 91 |
Equivalence of DFA and NFA | Ch 2.3 | |
| Sun, 16 - 07 - 91 |
State reduction | Ch 2.4 | HW2 | Sol-HW2 |
| Sat, 22 - 07 - 91 |
Regular Expressions | Ch 3.1 | |
| Sun, 23 - 07 - 91 |
Regular Expressions for Regular Languages |
Ch 3.2 | HW3 To be solved in class |
| Sat, 29 - 07 - 91 |
Grammars | Ch 1.3 | |
| Sun, 30 - 07 - 91 |
Regular Grammars | Ch 3.3 | HW4
To be solved in class |
| Sat, 06 - 08 - 91 |
Properties of Regular Languages | Ch 4.1, Ch 4.2 | |
| Sun, 07 - 08 - 91 |
Pumping Lemma for Regular Languages |
Ch 4.3 | HW5
To be solved in class |
| Sat, 13 - 08 - 91 |
[ Holiday ] | ||
| Sun, 14 - 08 - 91 |
Problem solving | HW3, HW4, HW5 | |
| Sat, 20 - 08 - 91 |
Problem solving | HW3, HW4, HW5 | |
| Sun, 21 - 08 -91 |
Contex Free Grammars | Ch 5.1 | |
| Sat, 27 - 08 - 91 |
Parsing and Ambiguity | Ch 5.2 | |
| Sun, 28 - 08 - 91 |
Simplicification of CF Grammars | Ch 6.1 | |
| Sat, 04 - 09 - 91 |
[ Holiday ] | ||
| Sun, 05 - 09 - 91 |
[ Holiday ] | ||
| Sat, 11 - 09 - 91 |
Normal Forms | Ch 6.2 | |
| Sun, 12 - 09 - 91 |
Non-deterministic Pushdown Automata | Ch 7.1 | HW6 To be solved in class |
| Sat, 18 - 09 - 91 |
PDAs and CF Languages | Ch 7.2 | |
| Sun, 19 - 09 - 91 |
Deterministic PDA Pumping Lemma for NPDAs |
Ch 7.3, Ch 7.4 | |
| Sat, 25 - 09 - 91 |
Properties of CF Languages | Ch 8.1 | |
| Sun, 26 - 09 - 91 |
Standard Turing Machines | Ch 8.1 Ch 8.2 |
HW 7 |
| Sat, 02 - 10 - 91 |
Turing Machines for Complictaed Tasks | Ch 9.2, Ch 9.3 | |
| Sun, 03 - 10 - 91 |
Hierarchy of Formal Languages and Automata |
Ch 11 | |
| Sun, 30 - 10 - 91 |
Final Exam | All syllabuses | Midterm-902 |
Sol
Final-902 | Hints |
