Theory of Computing

(3-4 Credit Hours) · Undergraduate

Introduction to formal languages and automata, computability theory, and complexity theory with the goal of developing understanding of the power and limits of different computational models. Topics covered include: regular languages and finite automata; context-free grammars and pushdown automata; Turing machines; undecidable languages; the classes P and NP; NP completeness. IT - Trinity College - Dublin: On successful completion of this module, students will be able to: LO1 understand and work with implementations of Finite State Automata and regular languages appreciating both their strengths and weakness and the areas of language processing to which they might be applied LO2 understand and work with implementations of context-free grammars and parsers, including stack-based and chart parsers. LO3 understand and work with implementations of probabilistic methods in language processing such as statistical parsers, the use of Hidden Markov Models for speech recognition or statistical machine translation LO4 understand the uses to which Feature Structures may be put in grammars of natural languages LO5 understand some aspects of recursive computations on grammatical structures to serve semantic ends