К содержимому
learnspaceYOUR NEXT CHAPTER
ПРОСТРАНСТВО ОБУЧЕНИЯ
ГлавнаяКаталог курсовМоё обучениеCoursera

Знания без границ

Учитесь у лучших университетов и компаний мира.

Открыть Coursera
Интеграция
Пространство университета
Моё пространствоСтраница курса
↵
ЯЛичный кабинетСтудент
© 2026 LearnSpaceКаждый день — возможность узнать больше.Помощь
Formal Languages and Applications · LearnSpace
Назад в каталог
courseraПрограммирование

Formal Languages and Applications

Курс от Birla Institute of Technology & Science, Pilani
Средний≈ 61.5 чАнглийский
О курсеНавыкиПрограммаПреподаватели

О курсе

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.

Навыки, которые вы освоите

Theoretical Computer ScienceComputer ProgrammingAlgorithmsComputer ScienceFormal LearningProgram DevelopmentSoftware EngineeringTechnical AnalysisData Science

Программа курса

10 модулей · 398 учебных материалов

01Elements40 материалов

Course Introduction

Course OverviewЧтениеMeet Your Instructor - Prof. S.P. VimalВидеоMeet Your Instructor - Prof. Kunal KorgaonkarВидеоCourse Introductory VideoВидео

Учитесь у экспертов

BITS Pilani Instructors Group

Преподаватель курса

Formal Languages and Applications
В каталоге вашей программы

Инвестируйте в себя

Новые знания — в удобное для вас время.

Начать на Coursera

Обучение откроется на Coursera
в новой вкладке

Обучение на Coursera

≈ 61.5 ч

10 модулей

Язык: Английский

Часть программы вашего университета
Course Structure & Critical InformationЧтение
Language Theory NavigatorDIALOGUE

Strings and Alphabets

IntroductionВидеоIntroducing AlphabetsВидеоRecommended Reading: Introducing AlphabetsЧтениеIntroducing AlphabetsЗаданиеIntroducing StringsВидеоRecommended Reading: Introducing StringsЧтениеIntroducing StringsЗаданиеOperations - Concatenation & ReverseВидеоRecommended Reading: Operations - Concatenation & ReverseЧтениеOperations - Concatenation & ReverseЗаданиеOperations - Prefix, Suffix & SubstringВидеоRecommended Reading: Operations - Prefix, Suffix & SubstringЧтениеOperations - Prefix, Suffix & SubstringЗаданиеKleene Star [Σ*]ВидеоRecommended Reading: Kleene Star [Σ*]ЧтениеKleene Star [Σ*]ЗаданиеProperties on String Operations - A ProofВидеоRecommended Reading: Properties on String Operations - A ProofЧтениеProperties on String Operations - A ProofЗадание

Languages

Introducing LanguagesВидеоRecommended Reading: Introducing LanguagesЧтениеIntroducing LanguagesЗаданиеOperations on LanguagesВидеоRecommended Reading: Operations on LanguagesЧтениеOperations on LanguagesЗадание

Grammar and Automata

Introduction to GrammarВидеоRecommended Reading: Introduction to GrammarЧтениеIntroduction to GrammarЗаданиеIntroduction to AutomataВидеоRecommended Reading: Introduction to AutomataЧтениеIntroduction to AutomataЗадание

Summary and Assessment

Summary of Module on ElementsВидеоLet's Practice: ElementsЗаданиеTest Yourself: ElementsЗадание
02Regular Languages, Regular Expressions and DFA61 материалов

Regular Expression and Regular Languages

Introducing Regular Expressions ВидеоRecommended Reading: Introducing Regular Expressions ЧтениеIntroducing Regular Expressions ЗаданиеAn Advice on Writing RE’sВидеоRecommended Reading: An Advice on Writing RE’sЧтениеAn Advice on Writing RE’sЗаданиеDefinition of Regular ExpressionsВидеоRecommended Reading: Definition of Regular ExpressionsЧтениеDefinition of Regular ExpressionsЗаданиеLanguages Associated with REsВидеоRecommended Reading: Languages Associated with Regular ExpressionsЧтениеLanguages Associated with Regular ExpressionsЗаданиеProblem Solving – Language for RE (1)ВидеоRecommended Reading: Problem Solving – Language for RE (1)ЧтениеProblem Solving – Language for RE (1)ЗаданиеProblem Solving – Language for RE (2)ВидеоRecommended Reading: Problem Solving – Language for RE (2)ЧтениеProblem Solving – Language for RE (2)ЗаданиеProblem Solving – RE for a Language (1)ВидеоRecommended Reading: Problem Solving – RE for a Language (1)ЧтениеProblem Solving – RE for a Language (1)ЗаданиеProblem Solving – RE for a Language (2)ВидеоRecommended Reading: Problem Solving – RE for a Language (2)ЧтениеProblem Solving – RE for a Language (2)ЗаданиеRegular Language (using RE)ВидеоRecommended Reading: Regular Language (Using RE)ЧтениеRegular Language (Using RE)Задание

Deterministic Finite Automata and Regular Languages

Introducing Finite AutomataВидеоRecommended Reading: Introducing Finite AutomataЧтениеIntroducing Finite AutomataЗаданиеDeterministic Finite Automata (DFA) (1)ВидеоRecommended Reading: Deterministic Finite Automata (DFA) (1)ЧтениеDeterministic Finite Automata (DFA) (1)Задание

Grammar and Regular Languages

Grammars for Regular LanguagesВидеоRecommended Reading: Grammars for Regular LanguagesЧтениеGrammars for Regular LanguagesЗаданиеGrammars for Regular Languages (2)ВидеоRecommended Reading: Grammars for Regular Languages (2)ЧтениеGrammars for Regular Languages (2)Задание

Summary and Assessment

Module Closure (Summary)ВидеоLet's Practice: Regular Languages, Regular Expressions and DFAЗаданиеTest Yourself: Regular Languages, Regular Expressions and DFAЗадание
03Implementing DFA & Applications27 материалов

Implementing DFA

Direct Implementation of a Simple DFAВидеоRecommended Reading: Direct Implementation of a Simple DFAЧтениеDirect Implementation of a Simple DFAЗаданиеTable Driven ImplementationВидеоRecommended Reading: Table Driven ImplementationЧтениеTable Driven ImplementationЗаданиеDirect vs Table Driven ImplementationВидеоRecommended Reading: Direct vs Table Driven ImplementationЧтениеDirect vs Table Driven ImplementationЗадание

Lexical Analysers

Structure of a CompilerВидеоRecommended Reading: Structure of a CompilerЧтениеStructure of a CompilerЗаданиеWorking of a Lexical AnalyserВидеоRecommended Reading: Working of a Lexical AnalyserЧтениеWorking of a Lexical AnalyserЗадание

Lab Exercise and Assessment

Practice LabsЧтениеLet's Practice: Implementing DFA & ApplicationsЗаданиеTest Yourself: Implementing DFA & ApplicationsЗадание
04Reduction of States in DFA45 материалов

Simplifying DFA

Equivalent DFA’s ВидеоRecommended Reading: Equivalent DFA’s ЧтениеEquivalent DFA’sЗаданиеIndistinguishable StatesВидеоRecommended Reading: Indistinguishable StatesЧтениеIndistinguishable StatesЗаданиеApproach to Simplifying DFAВидеоRecommended Reading: Approach to Simplifying DFAЧтениеApproach to Simplifying DFAЗаданиеMark in Mark-Reduce MethodВидеоRecommended Reading: Mark in Mark-Reduce MethodЧтениеMark in Mark-Reduce MethodЗаданиеReduce in Mark-Reduce MethodВидеоRecommended Reading: Reduce in Mark-Reduce MethodЧтениеReduce in Mark-Reduce MethodЗаданиеMark-Reduce Method – Example (1)ВидеоRecommended Reading: Mark-Reduce Method – Example (1)ЧтениеMark-Reduce Method – Example (1)Задание 0*1* vs. 0n1n (where n≥1)ВидеоRecommended Reading: 0*1* vs. 0n1n (where n≥1)Чтение0*1* vs. 0n1n (where n≥1)ЗаданиеThe Myhill-Nerode TheoremВидеоRecommended Reading: The Myhill-Nerode TheoremЧтениеThe Myhill-Nerode TheoremЗадание

Pumping Lemma

Recommended Reading: Introducing Pumping Lemma ЧтениеIntroducing Pumping LemmaЗаданиеApplying Pumping Lemma ВидеоRecommended Reading: Applying Pumping Lemma ЧтениеApplying Pumping LemmaЗаданиеApplying Pumping Lemma (2)Видео

Closure Properties

Closure Under Set OperationsВидеоRecommended Reading: Closure Under Set OperationsЧтениеClosure Under Set OperationsЗаданиеClosure Under Reverse & Other OperationsВидеоRecommended Reading: Closure Under Reverse & Other OperationsЧтениеClosure Under Reverse & Other OperationsЗадание

Assessment

Let's Practice: Reduction of States in DFAЗаданиеTest Yourself: Reduction of States in DFAЗадание
05Context-Free Languages33 материалов

Introduction to CFG and CFL

Limitations of Regular Languages ВидеоRecommended Reading: Limitations of Regular Languages ЧтениеLimitations of Regular LanguagesЗаданиеRevisiting the Definition of GrammarВидеоRecommended Reading: Revisiting the Definition of GrammarЧтениеRevisiting the Definition of GrammarЗаданиеExample of CFG’s Languages Generated by CFG - 1ВидеоRecommended Reading: Example of CFG’s Languages Generated by CFG - 1ЧтениеExample of CFG’s Languages Generated by CFG - 1ЗаданиеExample of CFG’s Languages Generated by CFG - 2ВидеоRecommended Reading: Example of CFG’s Languages Generated by CFG - 2ЧтениеExample of CFG’s Languages Generated by CFG - 2ЗаданиеExample of CFG’s Languages Generated by CFG - 3ВидеоRecommended Reading: Example of CFG’s Languages Generated by CFG - 3ЧтениеExample of CFG’s Languages Generated by CFG - 3ЗаданиеLeft Most and Right Most Derivation - 1ВидеоRecommended Reading: Left Most and Right Most Derivation - Example 1ЧтениеLeft Most and Right Most Derivation - Example 1ЗаданиеRecommended Reading: Left Most and Right Most Derivation - Example 2ЧтениеLeft Most and Right Most Derivation - Example 2ЗаданиеContext-Free Languages and ApplicationsВидеоRecommended Reading: Context-Free Languages and ApplicationsЧтениеContext-Free Languages and ApplicationsЗаданиеIntroduction to Push-Down AutomataВидеоRecommended Reading: Introduction to Push-Down AutomataЧтениеIntroduction to Push-Down AutomataЗаданиеMembership in Languages, Equivalence of Languages, ApplicationsВидеоRecommended Reading: Membership in Languages, Equivalence in Languages, ApplicationsЧтениеMembership in Languages, Equivalence in Languages, ApplicationsЗадание

Summary and Assessment

Module Closure (Summary)ВидеоCFG Applications ExplorerDIALOGUELet's Practice: Context-Free LanguagesЗаданиеTest Yourself: Context-Free LanguagesЗадание
06Ambiguity in CFG54 материалов

Parsing and Ambiguity

What it Means to Verify if w ∈ LВидеоRecommended Reading: What it Means to Verify if w ∈ LЧтениеWhat it Means to Verify if w ∈ LЗаданиеMotivation for the Grammar to Specify Languages UnambiguouslyВидеоRecommended Reading: Motivation for the Grammar to Specify Languages UnambiguouslyЧтениеMotivation for the Grammar to Specify Languages UnambiguouslyЗаданиеExample 1 - Ambiguous GrammarВидеоRecommended Reading: Example 1 - Ambiguous GrammarЧтениеExample 1 - Ambiguous GrammarЗаданиеExample 2 - Ambiguous GrammarВидеоRecommended Reading: Example 2 - Ambiguous GrammarЧтениеExample 2 - Ambiguous GrammarЗаданиеExplanation of LemmaВидеоRecommended Reading: Explanation of LemmaЧтениеExplanation of LemmaЗадание

Simplification of CFG

Example 1 - Eliminating ProductionsВидеоRecommended Reading: Example 1 - Eliminating ProductionsЧтениеExample 1 - Eliminating ProductionsЗаданиеExample 2 - Eliminating ProductionsВидеоRecommended Reading: Example 2 - Eliminating ProductionsЧтениеExample 2 - Eliminating ProductionsЗадание

Introduction to Normal Form

What is Normal Form? Why is Normal Form? ВидеоRecommended Reading: What is Normal Form? Why is Normal Form? ЧтениеWhat is Normal Form? Why is Normal Form? Задание

Pumping Lemma for Context-Free Languages

Motivation with an ExampleВидеоRecommended Reading: Motivation with an ExampleЧтениеMotivation with an ExampleЗаданиеPumping Lemma StatementВидеоRecommended Reading: Pumping Lemma StatementЧтениеPumping Lemma StatementЗадание

Closure Properties of CFL

Closed Under Operations Union, Concatenation and Kleene-ClosureВидеоRecommended Reading: Closed Under Operations Union, Concatenation and Kleene-ClosureЧтениеClosed Under Operations Union, Concatenation and Kleene-ClosureЗаданиеNot Closed Under Intersection and ComplementationВидеоRecommended Reading: Not Closed Under Intersection and ComplementationЧтениеNot Closed Under Intersection and ComplementationЗадание

Decidable Properties on CFL

Deciding Whether L(G) is Empty and InfiniteВидеоRecommended Reading: Deciding Whether L(G) is Empty and InfiniteЧтениеDeciding Whether L(G) is Empty and InfiniteЗадание

Summary and Assessment

Module Closure (Summary) ВидеоLet's Practice: Ambiguity in CFGЗаданиеTest Yourself: Ambiguity in CFGЗадание
07Introduction to Parsing with Recursive Descent Parsing34 материалов

Introduction to Parsing as Recognising CFL

Introduction to ParsingВидеоRecommended Reading: Introduction to ParsingЧтениеIntroduction to ParsingЗаданиеApproaches to Look for DerivationВидеоRecommended Reading: Approaches to Look for DerivationЧтениеApproaches to Look for DerivationЗадание

Recursive Descent Parsing

How to Write Recursive Descent Parser ВидеоRecommended Reading: How to Write Recursive Descent ParserЧтениеHow to Write Recursive Descent ParserЗаданиеWriting a Recursive Descent Parser in CВидеоRecommended Reading: Writing a Recursive Descent Parser in CЧтениеWriting a Recursive Descent Parser in CЗадание

Summary and Assessment

SummaryВидеоParsing Problem SolverDIALOGUELet's Practice: Introduction to Parsing with Recursive Descent ParsingЗаданиеTest Yourself: Introduction to Parsing with Recursive Descent ParsingЗадание
08Parsing - LL(1)43 материалов

LL(1) Parsing Introduction

What is LL(1) Parsing?ВидеоRecommended Reading: What is LL(1) Parsing?ЧтениеWhat is LL(1) Parsing?ЗаданиеIntroducing (Predictive) Parsing Table and Using it to ParseВидеоRecommended Reading: Introducing (Predictive) Parsing Table and Using it to ParseЧтениеIntroducing (Predictive) Parsing Table and Using it to ParseЗадание

Nullable, First and Follow Tables

Construction of Nullable, First and Follow SetsВидеоRecommended Reading: Construction of Nullable, First and Follow SetsЧтениеConstruction of Nullable, First and Follow SetsЗаданиеConstruction Algorithm - Nullable, First and FollowВидеоRecommended Reading: Construction Algorithm - Nullable, First and FollowЧтениеConstruction Algorithm - Nullable, First and FollowЗадание

LL(1) Table Construction

Table Construction AlgorithmВидеоRecommended Reading: Table Construction AlgorithmЧтениеTable Construction AlgorithmЗаданиеParsing a String Using TableВидеоRecommended Reading: Parsing a String Using TableЧтениеParsing a String Using TableЗадание

Conflicts in LL(1) Parsing Table

What are Conflicts in LL(1) Parsing Table?ВидеоRecommended Reading: What are Conflicts in LL(1) Parsing Table?ЧтениеWhat are Conflicts in LL(1) Parsing Table?ЗаданиеResolving ConflictsВидеоRecommended Reading: Resolving ConflictsЧтениеResolving ConflictsЗадание

Summary and Assessment

SummaryВидеоLL Parsing ExplorerDIALOGUELet's Practice: Parsing - LL(1)ЗаданиеTest Yourself: Parsing - LL(1)Задание
09Parsing - LR(0) and Illustration LR(k)32 материалов

Weakness of LL(k) Parsers

What are the Weaknesses of LL(k) ParsersВидеоRecommended Reading: What are the Weaknesses of LL(k) ParsersЧтениеWhat are the Weaknesses of LL(k) ParsersЗадание

Shift Reduce Parser

Demonstration of Shift Reduce ParserВидеоRecommended Reading: Demonstration of Shift Reduce ParserЧтениеDemonstration of Shift Reduce ParserЗаданиеThe Need of LR Parsing TableВидеоRecommended Reading: The Need of LR Parsing TableЧтениеThe Need of LR Parsing TableЗадание

LR(0) Parsing

What is LR(0) Parsing?ВидеоRecommended Reading: What is LR(0) Parsing?ЧтениеWhat is LR(0) Parsing?ЗаданиеExample: LR(0) Parsing Table to Parse a StringВидеоRecommended Reading: Example: LR(0) Parsing Table to Parse a StringЧтениеExample: LR(0) Parsing Table to Parse a StringЗадание

Introducing LR(1) Parsing and LR(k) Parsing

What is LR(1) Parsing and LR(k) ParsingВидеоRecommended Reading: What is LR(1) Parsing and LR(k) ParsingЧтениеWhat is LR(1) Parsing and LR(k) ParsingЗадание

Hierarchy of Grammar Classes

Hierarchy of Grammar Classes Involving LL and LRВидеоRecommended Reading: Hierarchy of Grammar Classes Involving LL and LRЧтениеHierarchy of Grammar Classes Involving LL and LRЗадание

Summary and Assessment

SummaryВидеоLet's Practice: Parsing - LR(0) and Illustration LR(k)ЗаданиеTest Yourself: Parsing - LR(0) and Illustration LR(k)Задание
10Constituency Parsing for POS Tagging29 материалов

Application in POS Tagging

Introducing POS Tagging - The Task and ApplicationsВидеоRecommended Reading: Introducing POS Tagging - The Task and ApplicationsЧтениеIntroducing POS Tagging - The Task and ApplicationsЗаданиеCFG and POS TaggingВидеоRecommended Reading: CFG and POS TaggingЧтениеCFG and POS TaggingЗаданиеPOS Tagging as ParsingВидеоRecommended Reading: POS Tagging as ParsingЧтениеPOS Tagging as ParsingЗадание

Context Sensitive Grammar

Introduction to CSGВидеоRecommended Reading: Introduction to CSGЧтениеIntroduction to CSGЗаданиеReal World Example 1ВидеоRecommended Reading: Real World Example 1ЧтениеReal World Example 1ЗаданиеReal World Example 2

Chomsky Hierarchy

Intro to Grammar HierarchyВидеоRecommended Reading: Intro to Grammar HierarchyЧтениеIntro to Grammar HierarchyЗадание

Summary and Assessment

OverviewВидеоAdvanced Grammar SynthesizerDIALOGUELet's Practice: Constituency Parsing for POS TaggingЗаданиеTest Yourself: Constituency Parsing for POS TaggingЗадание

Course Wrap-Up

Course SummaryЧтение
Deterministic Finite Automata (DFA) (2)Видео
Recommended Reading: Deterministic Finite Automata (DFA) (2)Чтение
Deterministic Finite Automata (DFA) (2)Задание
Deterministic Finite Automata (DFA)(3)Видео
Recommended Reading: Deterministic Finite Automata (DFA) (3)Чтение
Deterministic Finite Automata (DFA) (3)Задание
Language Accepted by DFA (1)Видео
Recommended Reading: Language Accepted by DFA (1)Чтение
Language Accepted by DFA (1)Задание
Language Accepted by DFA (2)Видео
Recommended Reading: Language Accepted by DFA (2)Чтение
Language Accepted by DFA (2)Задание
Designing DFAВидео
Recommended Reading: Designing DFAЧтение
Designing DFAЗадание
RL as Language Accepted by DFAsВидео
RL as Language Accepted by DFAsЗадание
Recommended Reading: Automaton for Left Linear GrammarЧтение
Automaton for Left Linear GrammarЗадание
Approach to Design Lexical AnalyserВидео
Recommended Reading: Approach to Design Lexical AnalyserЧтение
Approach to Design Lexical AnalyserЗадание
Lexical Analyser Design Example-1Видео
Recommended Reading: Lexical Analyser Design Example-1Чтение
Lexical Analyser Design Example-1Задание
Recognising Longest MatchВидео
Recommended Reading: Recognising Longest MatchЧтение
Recognising Longest MatchЗадание
Recommended Reading: Applying Pumping Lemma (2) Чтение
Applying Pumping Lemma (2)Задание
Applying Pumping Lemma (3) Видео
Recommended Reading: Applying Pumping Lemma (3) Чтение
Applying Pumping Lemma (3)Задание
Recommended Reading: Applying Pumping Lemma (4) Чтение
Applying Pumping Lemma (4)Задание
Example 1Видео
Recommended Reading: Example 1Чтение
Example 1Задание
Example 2Видео
Recommended Reading: Example 2Чтение
Example 2Задание
Example 3Видео
Recommended Reading: Example 3Чтение
Example 3Задание
Examples Видео
Recommended Reading: ExampleЧтение
ExampleЗадание
Issues in the Expression Grammar ExampleВидео
Recommended Reading: Issues in the Expression Grammar ExampleЧтение
Issues in the Expression Grammar ExampleЗадание
Rewriting the Grammar: Eliminate Left RecursionВидео
Recommended Reading: Rewriting the Grammar: Eliminate Left RecursionЧтение
Rewriting the Grammar: Eliminate Left RecursionЗадание
Rewriting the Grammar: Left Factoring Видео
Recommended Reading: Rewriting the Grammar: Left Factoring Чтение
Rewriting the Grammar: Left Factoring Задание
Rewriting the Grammar: Non-Terminals in the GrammarВидео
Recommended Reading: Rewriting the Grammar: Non-Terminals in the GrammarЧтение
Rewriting the Grammar: Non-Terminals in the GrammarЗадание
Recursive Descent Parser for Rewritten Expressions Grammar Видео
Recommended Reading: Recursive Descent Parser for Rewritten Expressions Grammar Чтение
Recursive Descent Parser for Rewritten Expressions Grammar Задание
Drawbacks of Recursive Parsing Видео
Recommended Reading: Drawbacks of Recursive Parsing Чтение
Drawbacks of Recursive Parsing Задание
Nullable, First and Follow - Example 1Видео
Recommended Reading: Nullable, First and Follow - Example 1Чтение
Nullable, First and Follow - Example 1Задание
Nullable, First and Follow - Example 2Видео
Recommended Reading: Nullable, First and Follow - Example 2Чтение
Nullable, First and Follow - Example 2Задание
Code Demonstration for LL(1) in CВидео
Recommended Reading: Code Demonstration for LL(1) in CЧтение
Code Demonstration for LL(1) in CЗадание
Example 2 – LL(1) TableВидео
Recommended Reading: Example 2 – LL(1) TableЧтение
Example 2 – LL(1) TableЗадание
LL(2) and LL(k) ParsersВидео
Recommended Reading: LL(2) and LL(k) ParsersЧтение
LL(2) and LL(k) ParsersЗадание
Constructing LR(0) Parsing TableВидео
Recommended Reading: Constructing LR(0) Parsing TableЧтение
Constructing LR(0) Parsing TableЗадание
Parsing a String Using LR(0)Видео
Recommended Reading: Parsing a String Using LR(0)Чтение
Parsing a String Using LR(0)Задание
Recommended Reading: Parsing a String Using LR(0) - 2Чтение
Parsing a String Using LR(0) - 2Задание
Видео
Recommended Reading: Real World Example 2Чтение
Real World Example 2Задание
Applications Видео
Recommended Reading: Applications Чтение
Applications Задание