Formal Languages and Applications

Birla Institute Of Technology And Science–Pilani (BITS–Pilani) via Coursera

Go to class Write review

Overview

Coursera Flash Sale

40% Off Coursera Plus for 3 Months!

Grab it

Welcome to the "Formal Languages and Applications" course! This course provides a comprehensive exploration of formal language structures and computational models. It covers regular expressions, finite automata, context-free grammars, and parsing algorithms, examining how these frameworks form the mathematical basis for programming languages, compilers, and natural language processing. Learners will study the theoretical underpinnings of language recognition systems while analyzing their role in solving computational problems. Through hands-on programming projects, you'll develop lexical analyzers, parsers, and language recognition systems solving real-world problems. This balance of theory and practice builds both conceptual understanding and practical skills essential for computational problem-solving. Ideal for software engineers, computer science students, and professionals working in language processing, this course equips participants with the expertise needed to design, analyze, and implement advanced systems used across modern software and AI-driven technologies.

Syllabus

Elements

This module introduces the learners to the fundamental elements of formal languages. Topics introduced in this module are Alphabets, Strings, Operations on Strings, and Languages as a set of strings and their applications. We will discuss how to use the proof techniques to prove some properties of strings and languages. We assume the learners are already exposed to some basic proof techniques, which we can use directly with a brief review. The approach to cover the topics will be with representative pen and paper exercises.

Regular Languages, Regular Expressions and DFA

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.

Implementing DFA & Applications

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.

Reduction of States in DFA

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.

Context-Free Languages

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.

Ambiguity in CFG

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

Introduction to Parsing with Recursive Descent Parsing

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.

Parsing - LL(1)

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.

Parsing - LR(0) and Illustration LR(k)

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.

Constituency Parsing for POS Tagging

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.