This course introduces students to the theoretical foundation of computer science. It deals
with the definitions and properties of mathematical models of computation. Students will learn finite state machines, regular grammars and regular expressions that are used to solve
problems that can be encoded as regular languages. Besides, finite state transducers and
weighted finite state machines are also taught. The properties of regular languages will be
discussed. Students will also learn pushdown automata and context free grammars to solve
problem that can be defined as context free languages. The properties of context free
languages will be discussed. Finally, students will learn Turing machine which is the
theoretical computation model that can be used to model any algorithms that modern
computer can do. Finite state machines are applied in text processing, compilers, speech
recognition, machine translation and others. On the other hand, context-free grammars are
applied in artificial intelligence, programming languages, natural language processing and
others.