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
