Course Catalogue

LJMU Partner Taught

To provide knowledge of automata theory, formal language theory, limits of computation and their relation to Computer Science applications, including compilers.

Outline Syllabus:Regular expressions (Regex), deterministic finite automata (DFA), nondeterministic finite automata (NFA) and probabilistic finite automata (PFA) and their applications in Computer Science Conversions between Regexs, DFA and NFA, their closure properties and decision algorithms Context free/sensitive languages, pushdown automata and the pumping lemma Lexical analysis and parsing of programming languages and connections to Regexs and context free grammars Computability theory including Turing machines, the Halting problem and Post’s correspondence problem

Additional Information:This module provides an introduction to automata theory and formal language theory and emphasizes real life application where these ideas are applicable. Particular attention is paid to compiler design considerations using regular expressions and context free grammars. The module also investigates the limits of effective computation by studying undecidable problems.