COURSE NUMBER: CS_MJ12
TITLE: AUTOMATA AND FORMAL LANGUAGES
DEPARTMENT / PROGRAM: BSCS
SCHOOL: AGOO COMPUTER COLLEGE
SEMESTER AND SCHOOL YEAR: 2nd Semester,SY 2007-2008
INSTRUCTOR: Ms. Irlyn Janette E. Lomboy
COURSE DESCRIPTION
This course introduces the formal models of computing and their relation to formal languages.
COURSE OBJECTIVES (DESIRABLE OBJECTIVES)
At the end of this course, the student should be able to:
1. understand the principal models of computation such as finite automata, pushdown automata and Turing machines
2. recognize the correspondence of the different language classes to the models of computation
COURSE OUTLINE AND TIMEFRAME
TOPICS AND READINGS
1. Introduction
Computation
http://courses.cs.vt.edu/~cs4114/lectures/index.html
Types & Characteristics of Automata
http://courses.cs.vt.edu/~cs4114/lectures/index.html
Finite Automata
http://infolab.stanford.edu/~ullman/ialc/slides/slides2.pdf
http://infolab.stanford.edu/~ullman/ialc/jdu-slides.html
http://www.iu.hio.no/data/QIC/info3/node9.html
Sets, relations, strings and string operations
http://vanha.math.utu.fi/research/automata/autores.html
http://www.cs.uky.edu/~lewis/texts/theory/automata/autoprob.pdf
http://www.cs.wm.edu/~mliskov/s06_cs423/handouts/review.pdf
Operations on languages
2. Finite State Machines
http://www.iu.hio.no/data/QIC/info3/node9.html
http://infolab.stanford.edu/~ullman/ialc/slides/slides5.pdf
Deterministic Finite Automata
http://users.encs.concordia.ca/~grahne/hmu_slides/allinone.pdf
Non-deterministic Finite Automata
http://infolab.stanford.edu/~ullman/ialc/slides/slides5.pdf
Regular Expressions
http://infolab.stanford.edu/~ullman/ialc/slides/slides6.pdf
http://infolab.stanford.edu/~ullman/ialc/slides/slides7.pdf
3. Context-free Grammar
http://infolab.stanford.edu/~ullman/ialc/slides/slides7.pdf
PDA to CFG
http://infolab.stanford.edu/~ullman/ialc/slides/slides9.pdf
Push-down Automata
Normal Forms for Grammars
Chomsky Normal Form
http://infolab.stanford.edu/~ullman/ialc/jdu-slides.html
4. Pushdown Automata
Model
Configuration
Characteristics
State Diagram
Construction
http://infolab.stanford.edu/~ullman/ialc/slides/slides12.pdf
Pumping Lemma, Ogden's Lemma
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
http://infolab.stanford.edu/~ullman/ialc/slides/slides11.pdf
Closure Properties
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
5. Turing Machines
Model
Acceptance by Halting
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
Move and Language of a TM
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
Diagonalization
Classes of Language
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
Rice’s Theorem
http://user.it.uu.se/~pierref/courses/FLAT/chapters8-9.pdf
http://infolab.stanford.edu/~ullman/ialc/slides/slides13.pdf
SUGGESTED READINGS
Introduction to Computer Theory By Daniel; I.A. Cohen
COURSE REQUIREMENTS
Assignments, Quizzes, Exams, Blogs, Links, Term Paper, Tree Planting
CONSULTATION HOURS
Sunday, April 20, 2008
Course Outline / Syllabus
COURSE NUMBER: CS_MJ12
TITLE: AUTOMATA AND FORMAL LANGUAGES
DEPARTMENT / PROGRAM: BSCS
SCHOOL: AGOO COMPUTER COLLEGE
SEMESTER AND SCHOOL YEAR: 2nd Semester,SY 2007-2008
INSTRUCTOR: Ms. Irlyn Janette E. Lomboy
COURSE DESCRIPTION
This course introduces the formal models of computing and their relation to formal languages.
COURSE OBJECTIVES (DESIRABLE OBJECTIVES)
At the end of this course, the student should be able to:
1. understand the principal models of computation such as finite automata, pushdown automata and Turing machines
2. recognize the correspondence of the different language classes to the models of computation
COURSE OUTLINE AND TIMEFRAME
TOPICS AND READINGS
1. Introduction
Computation
Types & Characteristics of Automata
Finite Automata
Sets, relations, strings and string operations
Operations on languages
2. Finite State Machines
Deterministic Finite Automata
Non-deterministic Finite Automata
Regular Expressions
3. Context-free Grammar
PDA to CFG
Push-down Automata
Normal Forms for Grammars
Chomsky Normal Form
4. Pushdown Automata
Model
Configuration
Characteristics
State Diagram
Construction
Pumping Lemma, Ogden's Lemma
Closure Properties
5. Turing Machines
Model
Acceptance by Halting
Move and Language of a TM
Diagonalization
Classes of Language
Rice’s Theorem
SUGGESTED READINGS
Introduction to Computer Theory By Daniel; I.A. Cohen
COURSE REQUIREMENTS
Assignments, Quizzes, Exams, Blogs, Links, Term Paper, Tree Planting
CONSULTATION HOURS
TITLE: AUTOMATA AND FORMAL LANGUAGES
DEPARTMENT / PROGRAM: BSCS
SCHOOL: AGOO COMPUTER COLLEGE
SEMESTER AND SCHOOL YEAR: 2nd Semester,SY 2007-2008
INSTRUCTOR: Ms. Irlyn Janette E. Lomboy
COURSE DESCRIPTION
This course introduces the formal models of computing and their relation to formal languages.
COURSE OBJECTIVES (DESIRABLE OBJECTIVES)
At the end of this course, the student should be able to:
1. understand the principal models of computation such as finite automata, pushdown automata and Turing machines
2. recognize the correspondence of the different language classes to the models of computation
COURSE OUTLINE AND TIMEFRAME
TOPICS AND READINGS
1. Introduction
Computation
Types & Characteristics of Automata
Finite Automata
Sets, relations, strings and string operations
Operations on languages
2. Finite State Machines
Deterministic Finite Automata
Non-deterministic Finite Automata
Regular Expressions
3. Context-free Grammar
PDA to CFG
Push-down Automata
Normal Forms for Grammars
Chomsky Normal Form
4. Pushdown Automata
Model
Configuration
Characteristics
State Diagram
Construction
Pumping Lemma, Ogden's Lemma
Closure Properties
5. Turing Machines
Model
Acceptance by Halting
Move and Language of a TM
Diagonalization
Classes of Language
Rice’s Theorem
SUGGESTED READINGS
Introduction to Computer Theory By Daniel; I.A. Cohen
COURSE REQUIREMENTS
Assignments, Quizzes, Exams, Blogs, Links, Term Paper, Tree Planting
CONSULTATION HOURS
Subscribe to:
Posts (Atom)