To understand the different types of formal automata, their relative computational power, and their practical implementation.
To learn how to use grammars and formal languages in specifying complex problem descriptions.
To develop better skills in program design by viewing programs as an organization of automata and abstract data structures.
Policies
Attendance is not mandatory, but you will be responsible for all material
covered in class. Roll will be taken until I know all the students.
The grade will be based on a mid-term exam and five projects. The mid-term
exam will count as 25% of the grade. Most of the projects will be programming
exercises. As a general rule projects which are not completed on time will not
count toward the final grade.
References
Java In A Nutshell, by David Flanagan, O'Reilly & Associates, Inc., 1997.
Exploring Java, by Patrick Niemeyer and Joshua Peck, O'Reilly & Associates, Inc., 1997.
Algorithms, Robert Sedgewick, 1988.
Algorithms + Data Structures = Programs, Niklaus Wirth, 1976.
Data Structures, Theory and Practice, Berztiss, 1975.
Foundations of Computer Science, Aho and Ullman, 1992.
Introduction to Automata Theory, Languages and Computation, Hopcroft and Ullman, 1979.
Machines, Languages and Computation, Denning, Dennis and Qualitz, 1978.
Topics
Tokens, strings, grammars and formal languages.
Finite state machines, Push down automata, and Turing machines.