This module is designed to introduce regular languages, regular expressions to specify RL, and dfa as acceptors of regular languages. Theorems on the formal relationship between RE and DFA will be discussed intuitively. The learners will be introduced to grammars, specifically left-linear and right-linear grammars, and their role in generating regular languages. Theorems on the connection between regular languages, regular expressions, DFA, and Left Linear, and right Linear Grammars will be discussed intuitively with examples. The learner will be encouraged to look for practical applications of the concepts introduced.

This module focuses on the practical implementation of deterministic finite automata (DFA) through the development of a simple lexical analyser. Students will learn to represent DFA as transition tables, write pseudo-code for table-based computation, and implement these concepts in C programs. The module also explores the role of lexical analysis in language translation, the notion of lexical tokens, and the idea of the longest match in lexical analysers. By the end of the module, students can extend a lexical analyser to handle various tokens and reserved words, culminating in a programming exercise to apply these skills.

In this module, learners will explore reducing the number of states in a deterministic finite automaton (DFA). They will revisit the concept of equivalence classes, understand the Myhill-Nerode theorem, and learn its applications in state reduction. The module will cover the theorem's intuitive explanation and practical applications, present an algorithm for minimizing DFA states, and demonstrate the process through examples. The session will conclude with a discussion on the implications of state minimization in lexical analyzers and its benefits.

This module introduces us to the second formal language of our course, called Context Free Language (CFL), and its applications. In this module, we will learn the motivations for understanding CFL and how to write (Context free) Grammar to generate CFL. This module will use many examples to demonstrate how to write grammar and perform derivation. The session will also cover the applications of CFLs and provide a high-level introduction to push-down automata, which accept languages generated by CFGs.

This module introduces the concept of parsing and the significance of ambiguity in grammars. Parsing is crucial for verifying whether a string belongs to a language. The module explores the motivation behind unambiguous grammar specifications, particularly in programming languages, and provides methods to identify and eliminate ambiguity in grammars. Additionally, the session covers the simplification of context-free grammars (CFGs) by eliminating redundant or useless productions and introduces the concept and importance of normal forms, particularly Chomsky Normal Form (CNF).

In this module, learners will be introduced to the fundamentals of parsing, focusing on the recursive descent parsing technique. Through examples, pseudo-code, and hands-on demonstrations, students will gain a practical understanding of how recursive descent parsers work. They will learn how to implement and troubleshoot parsers for context-free grammars and address common challenges such as left recursion and grammar conflicts.

In this module, learners will be introduced to LL(1) parsing, a top-down parsing technique. The module will cover the construction of nullable, first, and follow sets, which are essential for building the LL(1) parsing table. Through examples and code demonstrations, learners will gain a practical understanding of constructing and using LL(1) parsing tables. The module will also address handling conflicts in LL(1) parsing and provide an overview of LL(k) parsing techniques.

In this module, learners will be introduced to bottom-up parsing techniques with detailed construction and implementation of LR(0) parsers. The need for bottom-up parsing, parsers with various look-ahead, their relative strengths, and applications will be discussed.

In this module, learners will explore the concepts of Part-of-Speech (POS) tagging, their applications in Natural Language Processing (NLP), and the role of Context-Free Grammars (CFG) and parsers in these processes. The module will provide insights into developing a POS Tagger as a top-down/bottom-up parsing as explained in the earlier modules. The module will also discuss other possible applications of Context-Free Languages.