Instructor   /   Grader:

• Instructor:   Dr. Yusu Wang	Grader:   Jeff Patterson
  Office Hour:         MWF 11:00 - 11:30am      Room:                   DL 487     Phone:                   292-1309     Email:                   yusu at cse ...       URL  :                   www.cse.ohio-state.edu/~yusu	Office Hours:         Tue: 11:30am -- 12:30pm      Room:                   CL 420      Email:                   patterson.432at osu ...

  
  

   

Course Description

     
    This course introduces students to the theory of computation via formal languages and models of computation. It focuses on regular languages and contex-free languages. In particular, topics include regular language/expression, deterministic and non-deterministic finite automata, the Pumping Lemma for non-regular languages, context-free languages and pushdown automata.

 
   

Textbook   /   Grading

•   Primary textbook: 

 Introduction to Languages and the Theory of Computation by J. Martin. 3rd Ed.,  McGraw-Hill book company, 2003    

•   Grading policy :

Assignments:   30%,    Midterm:   30%,    Final:   40%

   

Course Materials

• Schedule:
• Lec 1: Introduction. Concept of language, operations of language. (Ch 1, Ch 2.4).
• Lec 2: Review of Mathematical induction. Introduction to regular expression. (Ch 2.2, Ch 2.5, Ch 3.1)
• Lec 3: Examples of regular expressions. (Ch 3.1)
• Lec 4 -- 5: Concept of FA and examples of FA (Ch 3.2 -- 3.3)
• Lec 6: Set operations of regular languages (Union, intersetion, complement, etc) (Ch 3.5)
• Lec 7-8: Non-deterministic FA, examples and relation to FA. (Ch 4.1 -- 4.2)
• Lec 9 - 11: More on NFA. Introduction of NFA-\Lambda, and how to convert a RL to NFA-\Lambda (first part of the Kleene Theorem). (Ch 4.2 -- 4.3)
• Lec 12: Introduction to the Pumping Lemma. (Ch. 5.3)
• Lec 13--14: More on Pumping Lemma and non-regular languages. (Ch. 5.3)

• Handouts / Homework:
• All homeworks should be submitted IN CLASS on the day it is due. NO LATE HOMEWORK is accepted.
• Homework 1 is available (pdf). It is due on April 4 (Friday) in class.
• Homework 2 is available (pdf). It is due on April 11 (Friday) in class.
  • Solution to problem (2.2) is : (1^* 0 0^* 2 + 2)^* 1^*0^*
• Homework 3 is available (pdf). It is due on April 18 (Friday) in class.
• Homework 4 is available (pdf). It is due on April 28 (Monday) at the time of Midterm.
• Homework 5 is available (pdf). It is due on May 12 (Monday) in class.
• Homework 6 is available (pdf). It is due on May 16 (Friday) in class.
• Homework 7 is awailable (pdf). It is due on May 28th (Wed) in class.

   

Announcements:

• Midterm: April 28, time 7:30 -- 9:00pm, DL 480.
• Final: University standard schedule: June 5th, 11:30 am -- 1:18 pm, DL 0266
• May 5th (Monday): CLASS IS CANCELLED!