Note: The following provides a suggested course description,
objectives, and an outline. These may be modified pending discussion with
the Faculty Chairs, proposing faculty, and other curriculum
reviewers.
Course Description: Review of logic and set theory,
functions and relations, formal languages and grammars, finite-state
automata, pushdown automata, Turing machine.
Course Objectives: The major objective of this course
is to introduce the student to the concepts of theory of computation in
computer science. The student should acquire insights into the
relationship among formal languages, formal grammars, and automata.
Course Outline by Topical Areas:
- Review of logic and set theory. Set Operations and Cardinality.
Denumerable sets.
- Generalization and classification abstractions mechanisms.
- Formal Languages, and Grammars. BNF notation. Derivations and parse
trees.
- Corrupt productions and ambiguity in formal grammars.
- Finite-state automata. Accepters and transducers. Nondeterministic
vs. deterministic accepters. Regular expressions.
- Tuple descriptions of Mealy and Moore finite-state machines. State
diagrams and state tables. Sequence diagrams.
- Pushdown automata
- Context-free grammars
- Turing machines
