Athasit Surarerks

 

                        

 

 

2110 355 Formal Languages & Automata Theory
Course Syllabus

 

 

Credits
Department
Faculty
Semester
Instructor(s)







Formation
Hours/Week

3(3-0-6)
Computer Engineering
Engineering
First
Athasit Surarerks, Dr. en Inf.
Office 19-04, tel:0 2218 6989, athasit@cp.eng.chula.ac.th

ELITE, 20th floor ENG4, tel 0 2218 6376
Chate Patanothai, M.Sc. in EE&CE.
Office 19-04, SE Lab, tel:0 2218 6989, Chate.p@chula.ac.th

Chotirat Ratanamahatana, Ph. D.

Office 19-05, tel 0 2218 6993, ann@cp.eng.chula.ac.th


Bachelor of Engineering
3

 

Course Description          

Studies concepts of grammars, automata, languages, computability and complexity; the relationship between automata and various classes of languages; Turing machine and equivalent models of computation, the Chomsky hierarchy, context-free grammar, push-down automata, etc; lemmas and variants, closure properties and decision properties.

 

Evaluation

 

Homework

10%

Automata theory

30%

Pushdown automata

20%

Turing machine

40%

 

Text-book

 

John C. Martin

Introduction to Languages and The Theory of Computation (3rd edition)

References

 

J. Hopcroft & J. Ullamn

Daniel I.A. Cohen

Harry R Lewis & Christos H. Papadimitriou

Thomas A. Sudkamp

Michael Sipser

Introduction to Automata Theory, Languages, and Computation

Introduction to Computer Theory (2nd edition)

Element of the Theory of Computation (2nd edition)

Languages and Machines: An Introduction to the Theory of Computer Science (2nd edition)

Introduction to the Theory of Computation (2nd edition)

 

 

 

 

 

Chapter

Topics

 




 






Introduction
Relations, Functions and Recursive Definitions

Methods of Proof & Mathematical Induction
Exercises
Language

Recursively Defining Language

Regular Expression

Finite Automata

Finite State Automata with Output

Number of States

Transition Graphs

Nondeterministic Finite State Machine

Kleene's Theorem

Regular Languages

Regular Decidable

Decision Problem

 

Mathematical Preliminaries



Finite Specification of Languages