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