CMPS 3233: Theory of Computation

Spring semester 2011

Instructor: Dr. Nelson L. Passos
Office: Bolin Science Hall 126B
Office phone: 397-4129
E-mail: nelson.passos@mwsu.edu
Webpage: cs.mwsu.edu/~passos
Office Hours: MF         1:30 - 4:00 pm
  TR          9:30 - 12:00
Class Hours: MWF     9:00 - BO 320

Course Description:

Study of the computability and complexity of computer problems, beginning with a review of mathematical concepts and the discussion of the automata theory, including finite automata, push-down automata and Turing machines.

Text book:

Automata and Formal Languages Ė An Introduction, by D. Kelley.

Tentative Agenda (revised):

January                         February                         March                         April                         May                         Grading

January


Jan 17

Martin Luther King Holiday

Jan 19

Mathematical Foundations

Jan 21

Mathematical Foundations

Jan 24

Mathematical Foundations

Jan 26

Alphabets and Languages

Jan 28

Alphabets and Languages

Jan 31

Operations on Languages


February


Feb 2

SNOW STORM

Feb 4

SNOW STORM

 

Assignment # 1

Feb 7

Finite Automata

Feb 9

SNOW STORM

Feb 11

Finite Automata

 

Assignment # 2

Feb 14

Non Determinism

Feb 16

Equivalence of DFA and NFA

Feb 18

FA and Regular Expressions

 

Assignment # 2

Feb 21

Pumping Lemma

Feb 23

Regular Grammars

Feb 25

Context Free Grammar (CFG)

 

Assignment # 3

Feb 28

Chomsky Normal Form


March


Mar 2

Push Down Automata (PDA)

Mar 4

Push Down Automata (PDA)

Mar 7

Equivalence of PDA and CFG

Mar 9

Test # 1

Mar 11

Pumping Lemma for CFG

Mar 14

Spring Break

Mar 16

Spring Break

Mar 18

Spring Break

Mar 21

Pumping Lemma for CFG

Mar 23

Turing Machine - basics

Mar 25

Turing Machine - basics

 

Assignment # 4

Mar 28

Turing Machine

Mar 30

Variants of Turing Machines


April


Apr 1

Universal Turing Machines

 

Assignment # 5

Apr 4

Languages and Turing Machines

Apr 6

Recursive Languages

Apr 8

Recursive Enumerable Languages

 

Assignment # 6

Apr 11

Context Sensitive Languages

Apr 13

Context Sensitive Languages

Apr 15

Undecidable Problems

Apr 18

Halting Problem

Apr 20

Postís Correspondence Problem

Apr 22-

Easter Break

Apr 25

Postís Correspondence Problem

Apr 27

Undecidability and  CFG

Apr 29-

Test # 2


May


May 2

Complexity

May 4

Space Complexity

May 6

Time Complexity

May 9

Finals (Monday, 8:00 am)


Grading



Tests: 25 % (each)
Final Exam: 20 %
Assignments: 25 %
Class Participation: 5 %


E-mail address:

nelson.passos@mwsu.edu

Back to Dr. Passos Home Page