Course Overview:
This course presents both the theory of finite automata, regular expressions, context free
grammars and push down automata. It also includes a short introduction to Turing
machines.
Finite automata and regular expressions are one of the first and simplest models of
computations. Their mathematical theory is quite elegant and simple. Finite automata are
widely used in applications (traffic light, lexical analysis, pattern search algorithm,
vending machines, etc...), and constitute a perfect illustration of basic concepts in set
theory and discrete structure. Context-free grammars have important applications in
syntactic analysis of both programming and natural language.
Turing machines were described by Alan Turing in 1937 and they are a powerful model
of computation since they help computer scientists understand the limits of mechanical
computation by providing a precise definition of an 'algorithm' or 'mechanical procedure'.
This course also explores the principles, algorithms, and data structures involved in the
design and construction of compilers. Topics include finite-state machines, lexical
analysis, context-free grammars, push-down parsers, LR and LALR parsers, other parsing
techniques, symbol tables, error recovery, and an introduction to intermediate code
generation.
1 Introduce concept in automata theory
2 Identify different formal language classes and their relationships
3 Design grammars and recognizers for different formal languages
4 Introduce the major concept areas of language translation and compiler
design
5 Differentiate Scanner and Parser phases of compiler
6 Extend the knowledge of parser by parsing LL Parser and LR Parser
- Teacher: VASUDEVA PAI -