## COT 5420 -- Theory of Computation I## Fall 2004## Mondays and Wednesdays, 5:00-6:15, ECS 143 |

- MAD 3512 (Formal Languages and Automata)

- Geoffrey Smith
- Office: ECS 320
- Telephone: 305 348-6037
- E-mail:
*smithg @ cs.fiu.edu* - Web: http://www.cs.fiu.edu/~smithg/
- Office Hours: Mondays and Wednesdays, 3:30 -- 4:45

I'll usually be happy to meet at other times. Send e-mail, call, or drop by.

"Algebraic Lower Bounds for Finite Automata" by Daniel Cazalis and Geoffrey Smith (manuscript, 2004).

In this course, we study a number of mathematical models of computation.
Our goal is to understand what can and what cannot be computed using
each of these models; this will give us insight into the resources
required to solve different problems.
One of the most remarkable things that we will learn is that some
problems cannot be solved by *any* computer algorithm.
Thus we will see fundamental limits on the power of computers.

Much of what we learn in this class has important practical applicability.
For example, *regular expressions* and *context-free grammars*
are widely used in text-processing applications to specify lexical and
syntactic structure.
At the same time, it should be recognized that much of the appeal of
this subject is purely aesthetic.
So to be happy in this course we must try to agree with Keats,
at least a little, that

“Beauty is truth, truth beauty,—that is all

Ye know on earth, and all ye need to know.”

The course will be structured as follows:

- Mathematical Preliminaries (Chapter 0). Notation, proof by induction, etc.
- Regular Languages (Chapter 1). Deterministic and nondeterministic finite automata, regular expressions, the pumping lemma for regular languages, minimal DFAs and NFAs.
- Context-Free Languages (Chapter 2). Context-free grammars, pushdown automata, the pumping lemma for context-free languages.
- Recursive and Recursively-Enumerable Languages (Chapters 3, 4, and some of 5). Turing machines, undecidability, reducibility.

Problem solving is the heart of this course.
What you get out of this course will mostly depend on how much effort
you put into solving the homework problems.
I will be assigning homework every couple of weeks;
also, I encourage you to think about *all* the exercises and problems
in the textbook, whether assigned or not.
Finally, I will sometimes designate problems as Bonus Problems;
these are challenging problems that I find especially interesting.
Solving them earns extra credit.

The final exam will be on Wednesday, December 15, from 3:30 to 6:15.

Homework 30% Midterm Exam 20% Final Exam 45% Class Participation 5%

Finally, I encourage you to make a serious effort to solve the problems on your own before you consult other books or other students. Struggling with different approaches to difficult problems will give you many insights that you won't get by simply reading a beautifully polished answer in a book. (Of course, after you've solved a problem on your own, it's then nice to look at other people's solutions to see how they compare with yours.)

Back to COT 5420 home page.