- To familiarize the students with the concept of formal languages, different classes of formal languages such as regular languages, context-free languages, context-sensitive languages, recursive and recursively enumerable languages.
- To familiarize students with the grammars and machines used for describing various types of languages. These include regular expressions, finite state automata, context-free grammars, push-down automata and Turing machines.
- To familiarize students with properties of different types of languages.
COURSE LEARNING OUTCOMES (CLO)
CLO: 1. Describe the role of abstract computational models to define which computational problems are solvable and which are not (C2-Comprehension).
CLO: 2. Define formal languages and their description in the form of formal grammars (C3-Application).
CLO: 3. Design grammars and models for different languages (C5- Synthesis).
- Introduction to Formal Languages
- Regular expressions and finite automata
- Non-deterministic automata
- Transition graphs and Kleene’s Theorem
- Operations on languages
- Closure properties of regular languages
- Pumping lemma
- Mealy and Moore Machines
- Push-down automata
- Context-free grammars
- Parse trees, ambiguity and non-determinism
- Chomsky Normal Form
- Pumping Lemma for Context Free Languages
- Turing machines and Turing computability