COURSE OBJECTIVES

  • 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).

COURSE CONTENTS

  1. Introduction to Formal Languages
  2. Regular expressions and finite automata
  3. Non-deterministic automata
  4. Transition graphs and Kleene’s Theorem
  5. Operations on languages
  6. Closure properties of regular languages
  7. Pumping lemma
  8. Mealy and Moore Machines
  9. Push-down automata
  10. Context-free grammars
  11. Parse trees, ambiguity and non-determinism
  12. Chomsky Normal Form
  13. Pumping Lemma for Context Free Languages
  14. Turing machines and Turing computability