Introduction to Formal Languages

 -- Undergraduate, 2012 Spring

• Goal: Teach formal languages, computation model and theory of modern computers

• Textbook

  •  Peter Linz, An Introduction to Formal Languages and Automata (5th ed.), Jones & Bartlett Learning, 2012.

• Pre-course: discrete mathematics, data structures

• Class hours/place: 2EF,5B/EC015

• Office hours: 1:30-3:00pm, Wednesday & Friday

• Grading:

  • Homework: 35%

    • Homework #1, due 3/20/2012 (Tuesday) [reference solutions]

    • Homework #2, due 4/6/2012 (Friday)  [reference solutions]

    • Homework #3, due 5/8/2012 (Tuesday) [reference solutions]

    • Homework #4, due 6/8/2012 (Friday) [reference solutions]

  • Midterms (twice): 40%

    • Midterm I, 4/10/2012 (Tuesday)

    • Midterm II, 5/15/2012 (Tuesday) !!!

    • Final 6/12/2012 (Tuesday) !!!

  • Final: 25% 

• TA:

  • 沈宣佐 vink.cs95g@nctu.edu.tw

  • Place: EC 229A

  • Office hours:  10:30am~12:00, Tue & Thu @ EC229A

• Syllabus

  • Introduction [slides]

  • Finite automata [slides] [JFLAP tutorial]

  • Regular languages and regular grammars [slides]

  • Properties of regular languages [slides]

  • Context-free languages [slides]

  • Simplification of context-free grammars and normal forms [slides]

  • Pushdown automata [slides]

  • Properties of context-free languages [slides]

  • Turing machines [slides]

  • Other models of Turing machines [slides]

  • Busy beaver [slides]

  • Limits of algorithmic computation

  • An overview of computational complexity

-- last update: 2012/06/09