Introduction to Automata Theory & Languages
Textbook:
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman’s book is very appropriate for our course and in its third edition, it covers all the things we need in our course. If you like you can use this book instead of Peter Linz’s book, and you will be able to follow all the lectures, and find corresponding chapters which cover our lectures in this book.
We use Peter Linz ’s book, because it is very good narrated and has solid examples. The other reason for using this book as our textbook is that, Linz's book is the first referentce which our curriculum has suggested.
|
An Introduction to Formal Languages and Automata, 4/E
Peter Linz, University of California Copyright 2006, 415 p. ISBN-13: 9780763737986 ISBN-10: 0763737984 Publisher: Jones and Bartlett |
||
| Reference Book: | |||
|
Introduction to Automata Theory, Languages, and Computation, 3/E
John E. Hopcroft, Cornell University Rajeev Motwani, Stanford University Jeffrey D. Ullman, Stanford University Copyright: 2007 ISBN-10: 0321462254 ISBN-13: 9780321462251 Publisher: Addison-Wesley |
|
Introduction to the Theory of Computation, 2nd Edition
Michael Sipser - MIT Copyright: 2006, 400 p. ISBN-10: 0534950973 ISBN-13: 978053495097 Publisher: Addison-Wesley |
Some notes about the textbook and the reference books:
Michael Sipser's book is one of the greatest books in the field of computability and complexity, but the book covers more the advanced topics, rather the subjects we should study more, according to our curriculum. I will use good examples of this book in class throughout the semester.John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman’s book is very appropriate for our course and in its third edition, it covers all the things we need in our course. If you like you can use this book instead of Peter Linz’s book, and you will be able to follow all the lectures, and find corresponding chapters which cover our lectures in this book.
We use Peter Linz ’s book, because it is very good narrated and has solid examples. The other reason for using this book as our textbook is that, Linz's book is the first referentce which our curriculum has suggested.
Schedule :
Announcements:
I will be available in my office tomorrow (1 Bahman 1388) from 8:00 am to 9:30 am to answer your questions.
Homework, Exams, and Grades
This file will be updated throughout the semester and contains homework and programming assginments.
Homework #1 is uploaded. Due date for this homework is Saturday, October 10, 2009.
Homework #2 is uploaded. Due date for this homework is Monday, October 26, 2009.
Homework #3 is uploaded. Due date for this homework is Monday, November 02, 2009.
Final Exam:
Homework #1 is uploaded. Due date for this homework is Saturday, October 10, 2009.
Homework #2 is uploaded. Due date for this homework is Monday, October 26, 2009.
Homework #3 is uploaded. Due date for this homework is Monday, November 02, 2009.
Homework #4 is uploaded. Due date for this homework is Friday, December 11, 2009.
Midterm Exam:Final Exam:
Grading
Homework and programming assignments: 25%
Midterm exam: 30%
Final exam: 40%
Class participation: 5%
Midterm exam: 30%
Final exam: 40%
Class participation: 5%
Previous Exams
Lecture Slides
In This set of slides we examine the meaning of "Automata Theory and Languages".
We study what automaton is and we see there are different kinds of automata. Next we examine the meaning of alphabet, string, and language.
Download the second set of slides. In this set of slides we introduce Deterministic Finite Automaton and present its formal definition. We also use some examples to see how it works.
Download this tutorial in which it is explained how one can determine the language of an automaton.
Our third set of slides are uploaded here. In this slide set we covers NFAs (Nondeterministic Finite Automata). We see the way NFA works using some examples and also formal definition of NFAs. We also prove that they are as powerful as DFAs i.e. they accept Regular Languages akin to DFAs.
Our frouth set of slides are uploaded here. In this slide we study regular languages' properties. We prove regular languages are closed under union, concatenation, star, reversal, complement, and intersection operators.
The 5th set of slides!. In this set of slides we introduce regular expressions and exhibit that the set of languages we can construct on regular expressions is equal to the set of regular languages. We also demonstrate methods by which one can convert a DFA to its corresponding regular expression, and convert a regular expression to its corresponding DFA.
Here you can download the new set of slides. In this set of slides we firstly introduce pigeonhole principal, in order to establish the foundation for pumping lemma. Pumping lemma is a method by which one can determine whether a language is regular or not. We also see some examples on pumping lemma's application.
Here you can download the new set of slides. 3 examples in which we use Pumping Lemma are solve in this slide set and by that we show the languages under discussion are not regualar.
Click here to download the new attractive slides! Using this set of slides we introduce a bigger class of languages called Context Free Languages. We also learn that grammars are a way for describing languages. We see how one can write a derivation and depict a derivation tree for a sentence. Finally we see what ambiguity is and we describe the notion of ambiguity.
Click here to download the new set of slides. We learn how one can simplify a CFG. We learn some rules which help us to remove the redundant non-terminals and useless production rules. We also learn how to convert a CFG to its equivalent Chomsky and Greinbach Normal Form.
Click here to download the attractive slides of this session! CFGs are used in compilers. We study how Exhaustive parsers, and CYK parsers work, and we also examine their time complexity. We also introduce S-Grammars in this session.
Click here to download the slides of this session! We examine Linear Grammars and observe that special kind of linear grammars (Left-Linear Grammars and Right-Linear Grammars) generate regular languages. We also learn how one can convert a DFA to a Right-Linear Grammar and vice versa.
Click here to download the attractive slides of this session! In this set of slides we study what Push Down Automata (PDA) is, and see how it works. We also define it formally.
Click here to download the attractive slides of this session! In this set of slides we prove that PDAs accept Context Free Languages. Meanwhile we learn how to convert a CFG to its equivalent PDA and vice versa.
Click here to download the attractive slides of this session! In this set of slides we speak about properties of CFLs. We see they are closed set under union, concatenation, and star operation. We also see that CFLs set is not closed under intersection and complement. We also examine regular intersection closure and use this property to solve some problems.
Click here to download the attractive slides of this session! We learn how the restricted version of PDA (DPDA: Deterministic Pushdown Automata) works and prove that they are subset of PDAs.
Click here to download the attractive slides of this session! Turing Machine is our last subject.
Download the second set of slides. In this set of slides we introduce Deterministic Finite Automaton and present its formal definition. We also use some examples to see how it works.
Download this tutorial in which it is explained how one can determine the language of an automaton.
Our third set of slides are uploaded here. In this slide set we covers NFAs (Nondeterministic Finite Automata). We see the way NFA works using some examples and also formal definition of NFAs. We also prove that they are as powerful as DFAs i.e. they accept Regular Languages akin to DFAs.
Our frouth set of slides are uploaded here. In this slide we study regular languages' properties. We prove regular languages are closed under union, concatenation, star, reversal, complement, and intersection operators.
The 5th set of slides!. In this set of slides we introduce regular expressions and exhibit that the set of languages we can construct on regular expressions is equal to the set of regular languages. We also demonstrate methods by which one can convert a DFA to its corresponding regular expression, and convert a regular expression to its corresponding DFA.
Here you can download the new set of slides. In this set of slides we firstly introduce pigeonhole principal, in order to establish the foundation for pumping lemma. Pumping lemma is a method by which one can determine whether a language is regular or not. We also see some examples on pumping lemma's application.
Here you can download the new set of slides. 3 examples in which we use Pumping Lemma are solve in this slide set and by that we show the languages under discussion are not regualar.
Click here to download the new attractive slides! Using this set of slides we introduce a bigger class of languages called Context Free Languages. We also learn that grammars are a way for describing languages. We see how one can write a derivation and depict a derivation tree for a sentence. Finally we see what ambiguity is and we describe the notion of ambiguity.
Click here to download the new set of slides. We learn how one can simplify a CFG. We learn some rules which help us to remove the redundant non-terminals and useless production rules. We also learn how to convert a CFG to its equivalent Chomsky and Greinbach Normal Form.
Click here to download the attractive slides of this session! CFGs are used in compilers. We study how Exhaustive parsers, and CYK parsers work, and we also examine their time complexity. We also introduce S-Grammars in this session.
Click here to download the slides of this session! We examine Linear Grammars and observe that special kind of linear grammars (Left-Linear Grammars and Right-Linear Grammars) generate regular languages. We also learn how one can convert a DFA to a Right-Linear Grammar and vice versa.
Click here to download the attractive slides of this session! In this set of slides we study what Push Down Automata (PDA) is, and see how it works. We also define it formally.
Click here to download the attractive slides of this session! In this set of slides we prove that PDAs accept Context Free Languages. Meanwhile we learn how to convert a CFG to its equivalent PDA and vice versa.
Click here to download the attractive slides of this session! In this set of slides we speak about properties of CFLs. We see they are closed set under union, concatenation, and star operation. We also see that CFLs set is not closed under intersection and complement. We also examine regular intersection closure and use this property to solve some problems.
Click here to download the attractive slides of this session! We learn how the restricted version of PDA (DPDA: Deterministic Pushdown Automata) works and prove that they are subset of PDAs.
Click here to download the attractive slides of this session! Turing Machine is our last subject.
Teaching Assistant
Reza Sabeti is my TA in this course this semester.
If you have any question just contact him
and ask your question.
 Reza Sabeti |