Formal Languages and Automata Theory
 Class sessions: Tuesday and Thursdays 11:30-13:00

Professor:
  Dr. Luis Pineda
  lpineda@leibniz.iimas.unam.mx
  Department of Computer Science
  IIMAS, UNAM
  Tel: 562-23618

Content:
  • Texts
  • Additional readings
  • Tentative schedule
  • Grading policy

    • Textos
  • Introduction to Languages and the Theory of Computation (Third edition) John Martin, McGraw Hill, 2003
  • Introduction to Automata Theory, Languages and Computation (Second Edition) John E. Hopcroft, Rajeev Motwani and Jeffery D. Ullman Addison Wesley, 2001
    • Additional lectures:
  • Computability and Logic (Third Edition) George S. Boolos and Richard C. Jeffrey Cambridge University Press, 1989.
    • Tentative schedule:
     
    Clases
    		 Title Readings 1 Additional readings2 , 3 Homeworks Solutions Slides Color slides
    Ago 17 Presentations            
    Ago 19 Preliminaries and languages 1.5 1.5 BJ1     Sesión 1 Sesión 1
    Ago 24
    		 Languages and language operations 1.5
    1.5, 3.1.1 & BJ2
    		     Session 2 Session 2
    Ago 26
    		 Lenguages and regular expressions
    3.1
    3.1.2 & 3.1.3
    Homework 1
    Solution 1
    		 Session 3 Session 3
    Ago 31
    		 Examples and applications of regular languages
    3.1
    3.3
    		     Session 4 Session 4
    Sep 2
    		 Finate Automata
    3.2, 3.3
    		 2.1 & 2.2     Session 5 Session 5
    Sep 7
    		 The language accepted by a FA
    3.3, 3.4
    2.2.4 & 2.2.5
    Homework 2
    Solution 2
    		 Session 6 Session 6
    Sep 9
    		 FA operations
    3.5
    2.1 & 4.2.1
    		     Session 7 Session 7
    Sep 14
    		 non-deterministic FA
    4.1, 4.2
    2.3
    Homework 3
    Solution 3
    		 Session 8 Session 8
    Sep 21
    		 NAF are FA
    4.1
     2.3.5 & 2.3.6
    		     Session 9 Session 9
    Sep 23
    		 NFA with empty transitions
    4.2
    2.5
    		     Session 10 Session 10
    Sep 28
    		 Kleene Theorem
    4.3
     3.2
    Homework 4
    Solution 4
    		 Session 11 Session 11
    Sep 30
    		 Minimal Automaton
     5.1 & 5.2
    4.4
    		     Session 12 Session 12
    Oct 5
    		 Pumping lemma
    5.3
     4.1
    		     Session 13 Session 13
    Oct 7
    		 Midterm    
    Exam
    		      
    Oct 12
    		 Context Free Grammarstd>
    6.1
    5.2, 5.2
    Homework 5
    Solution 5
    		 Session 14 Session 14
    Oct 14
    		 CFL and RE
    6.2, 6.3
    5.3
    		     Sesión 15 Sesión 15
    Oct 19
    		 Ambigüedad
    6.4, 6.5, 6.6
    5.4 & 7.1
    		     Session 16 Session 16
    Oct 21
    		 Chomsky´s Normal Form (CNF)
    6.4, 6.5, 6.6
    5.4 & 7.1
    Homework 6
    Solution 6
    		 Session 17 Session 17
    Oct 26
    		 Push-Down Automata (PDA)
    7.1, 7.2
    6.1, 6.2
    		     Session 18 Session 18
    Oct 28
    		  Deterministic PDA
    7.3
    6.4
    		     Session 19 Session 19
    Nov 4
    		 PDA for CFG
    7.4
    6.2 & 6.3
    		     Session 20 Session 20
    Nov 9
    		 GLC de AP
    7.5
    6.2 & 6.3
    Homework 7
    Solution 7
    		 Session 21 Session 21
    Nov 11
    		 Top-down parsing
    7.6
    		       Session 22 Session 22
    Nov 16
    		 Bottom-up parsing
    7.6
    		       Session 23 Session 23
    Nov 18
    		 Pumping Lemma for CFL
    8.1
    6.2
    Homework 8
    Solutions 8
    		 Session 24 Session 24
    Nov 23
    		 Decision problems for CFL
    8.2, 8.3
    		          
    Nov 25
    		 Turing Machine and Church´s Thesis 9       Session 25 Session 25
    Nov 30
    		 Recursive languages and Chomsky´s Hierarchy 10          
    Dic 2
    		 Final            
    1 X.Y: John Martin, Cap. X, Sec. Y.
    2 X.Y: Readings from Hopcroft, Motwani and Ullman, unless otherwise specified
    3 BJX: Boolos and Jeffrey, Cap. X.
    Política de calificaciones
  • Homeworks:  30%
  • Midterms: 30%
  • Final 40%


    •