Home

Assignments

Handouts

Models of Computation

Spring 2007

COURSE INFORMATION

COURSETITLE: Models of Computation
COURSE NUMBER: CIS 361
PREREQUISITES: MTH 182, CIS 181

COURSE DESCRIPTION:
Models of sequential, parallel and distributed computations. Deterministic and non-deterministic finite automata, two-way finite automata, equivalence of automata, Mealy and Moore automata, regular languages, grammars and expressions and their relationship with finite automata, implementations of finite automata; pumping lemma and Myhill-Nerode theorem as two criteria of language regularity; push-down automata as acceptors of context-free languages, context-free grammars and their normal forms, pumping lemma for context-free languages; the Chomsky hierarchy; Turing machine as formal model for computable functions, for decision problems; the Church thesis. Introduction to computational complexity: time and space, complexity classes.

• to understand applications of computational models in computer science and especially in software engineering
• to understand relationship between formal languages in Chomsky hierarchy and machine models
• to understand criteria of regularity and context-freeness of formal languages
• to understand computational power of the Turing machine (general model of computation)
• hardware and software implementations of models of computations.

• individual proficiency in solving problems related to models of computations
• individual proficiency in applying software tools based on formal languages and models of computation
• ability to apply models of computation to small-scale software design.

TEXTBOOK:

1. John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Second edition, Assisob-Wesley, 2001, ISBN 0-201-44124-1.
2. Susan H. Rodger, Thomas W. Finley, JFLAP, An Interactive Formal Languages and Automata Package, Jones and Bartlet Publishers, 2006, ISBN 13-978-0-7637-3834-1.

COURSE SCHEDULE: T, Th 9.30.a.m.-10.45 a.m.,
Dion Science and Engineering Bldg., Room 101

Instructor: Dr. Boleslaw Mikolajczak
Dion Room 302F, phone: 999-8350; fax: 508-999-9144
Instructor’s Office hours: Tu, Th: 11.00 AM - 11.50 AM;
Fr: 1.00 - 2.45 pm
email: bmikolajczak@umassd.edu
Teaching Assistant: Aashay Joshi, Graduate CS major
office hours TBD; Dion 303 or 306
COURSE OUTLINE: 2
-------------------------------------------------------------------------------------------------------------------------------
Lecture Topic
-------------------------------------------------------------------------------------------------------------------------------
PART I: FINITE AUTOMATA AND REGULAR LANGUAGES:

1. Review of course contents; Deterministic and non-deterministic automata:
2. Subset construction for non-deterministic automata.
3. Finite automata and their implementations
4. Regular languages; synthesis of an automaton from regular language.
5. Analysis algorithm. Pumping lemma for regular languages
6. The Myhill-Nerode theorem for finite automata
7. Pumping lemma for regular languages. Two-way finite automata.
8. Decision problems for regular languages
9. Mealy's and Moore's automata and their equivalence
10. Regular grammars/regular languages/regular expressions
-------------------------------------------------------------------------------------------------------------------------------
PART II: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA:
11. Context-free grammars; parse trees, derivations and languages
12. Canonical forms of CFL: Chomsky and Greibach
13. Inherently ambiguous context-free languages; Pumping lemma for CFL
14. Push-down automaton: deterministic and non-deterministic; instantaneous description.
15. Equivalence of PDA's and CFL's.
16. Acceptance by the final state and the empty stack in the PDA
17. The CYK algorithm
-------------------------------------------------------------------------------------------------------------------------------
PART III: TURING MACHINES, COMPUTABILITY AND UNDECIDABILITY:
18. Turing machine; definition, instantaneous description
19. Techniques for TM construction; Modifications of TM's. Turing-Church thesis.
20. TM's as objects: computing functions, enumerators, modeling decision processes.
21. The Chomsky hierarchy: regular, context-free, context-sensitive, and r.e. languages;
22. Decidability, Unecidability. Reduction. Examples of undecidable problems
-------------------------------------------------------------------------------------------------------------------------------
PART IV: MODELS OF PARALLEL AND DISTRIBUTED COMPUTATIONS:
23. Models of distributed computations: Petri nets
24. Parallel programming constructs; RAM vs. PRAM
25. Models of parallel computations: shared memory, message passing
26. Course review and closing

1. All assignments in this course are assumed to be results of individual student work. Results of collective work will be evaluated as 0 points (both in homework and programming assignments).
2. Homework and programming assignments should be submitted to the instructor on time (not later than during class on the due date). Late delivery will be penalized by 20% decrease per day up to three days.
3. Read textbook and distributed HANDOUTS and participate regularly in class; some material presented in class in not contained in the textbook.
4. Ask questions (instructor of TA) if you don't understand the material.
5. Homework and programming assignments will be evaluated by TA during one-week period to give you prompt feedback.
6. Each homework assignment should contain title page with students name, name and number of the course, name of the instructor, number and type of assignments. Each problem should be solved on AN independent sheet of paper (each sheet should also contain student's name, course number, assignment number and problem number). All sheets should be stapled. Homework assignments should be prepared using word processor. Homework assignments should be submitted as a hardcopy only (no email please).