آموزش زبان‌های صوری و کاربردهای آن‌ها - آخرین آپدیت

سرفصل ها و درس ها

عناصر پایه Elements

• آشنایی با مدرس: پروفسور S.P. Vimal Meet Your Instructor - Prof. S.P. Vimal

• آشنایی با مدرس: پروفسور Kunal Korgaonkar Meet Your Instructor - Prof. Kunal Korgaonkar

• ویدئوی معرفی دوره Course Introductory Video

• مقدمه Introduction

• معرفی الفباها Introducing Alphabets

• معرفی رشته‌ها Introducing Strings

• عملیات الحاق و معکوس Operations - Concatenation & Reverse

• عملیات پیشوند، پسوند و زیررشته Operations - Prefix, Suffix & Substring

• ستاره کلین [Σ*] Kleene Star [Σ*]

• ویژگی‌های عملیات روی رشته‌ها - یک اثبات Properties on String Operations - A Proof

• معرفی زبان‌ها Introducing Languages

• عملیات روی زبان‌ها Operations on Languages

• مقدمه‌ای بر گرامر Introduction to Grammar

• مقدمه‌ای بر اتوماتا Introduction to Automata

• خلاصه بخش عناصر پایه Summary of Module on Elements

زبان‌های منظم، عبارت‌های منظم و DFA Regular Languages, Regular Expressions and DFA

• معرفی عبارت‌های منظم Introducing Regular Expressions

• توصیه‌هایی برای نوشتن عبارت‌های منظم An Advice on Writing RE’s

• تعریف عبارت‌های منظم Definition of Regular Expressions

• زبان‌های مرتبط با عبارت‌های منظم Languages Associated with REs

• حل مسئله - زبان برای عبارت منظم (۱) Problem Solving – Language for RE (1)

• حل مسئله - زبان برای عبارت منظم (۲) Problem Solving – Language for RE (2)

• حل مسئله - عبارت منظم برای یک زبان (۱) Problem Solving – RE for a Language (1)

• حل مسئله - عبارت منظم برای یک زبان (۲) Problem Solving – RE for a Language (2)

• زبان منظم (با استفاده از عبارت منظم) Regular Language (using RE)

• معرفی اتوماتاهای متناهی Introducing Finite Automata

• اتوماتای متناهی معین (DFA) - بخش ۱ Deterministic Finite Automata (DFA) (1)

• اتوماتای متناهی معین (DFA) - بخش ۲ Deterministic Finite Automata (DFA) (2)

• اتوماتای متناهی معین (DFA) - بخش ۳ Deterministic Finite Automata (DFA)(3)

• زبان پذیرفته شده توسط DFA (۱) Language Accepted by DFA (1)

• زبان پذیرفته شده توسط DFA (۲) Language Accepted by DFA (2)

• طراحی DFA Designing DFA

• زبان‌های منظم به عنوان زبان‌های پذیرفته شده توسط DFA RL as Language Accepted by DFAs

• گرامرهای زبان‌های منظم Grammars for Regular Languages

• گرامرهای زبان‌های منظم - بخش ۲ Grammars for Regular Languages (2)

• جمع‌بندی و خلاصه بخش Module Closure (Summary)

پیاده‌سازی DFA و کاربردها Implementing DFA & Applications

• پیاده‌سازی مستقیم یک DFA ساده Direct Implementation of a Simple DFA

• پیاده‌سازی مبتنی بر جدول Table Driven Implementation

• مقایسه پیاده‌سازی مستقیم و مبتنی بر جدول Direct vs Table Driven Implementation

• ساختار یک کامپایلر Structure of a Compiler

• نحوه عملکرد تحلیل‌گر لغوی Working of a Lexical Analyser

• رویکرد طراحی تحلیل‌گر لغوی Approach to Design Lexical Analyser

• مثال طراحی تحلیل‌گر لغوی ۱ Lexical Analyser Design Example-1

• تشخیص طولانی‌ترین تطبیق Recognising Longest Match

کاهش حالت‌ها در DFA Reduction of States in DFA

• DFAهای معادل Equivalent DFA’s

• حالت‌های غیرقابل تشخیص Indistinguishable States

• رویکرد ساده‌سازی DFA Approach to Simplifying DFA

• مرحله Mark در متد Mark-Reduce Mark in Mark-Reduce Method

• مرحله Reduce در متد Mark-Reduce Reduce in Mark-Reduce Method

• مثال متد Mark-Reduce (۱) Mark-Reduce Method – Example (1)

• مقایسه 0*1* در مقابل 0n1n (که در آن n≥1) 0*1* vs. 0n1n (where n≥1)

• قضیه Myhill-Nerode The Myhill-Nerode Theorem

• به‌کارگیری لمای پمپینگ (Pumping Lemma) Applying Pumping Lemma

• به‌کارگیری لمای پمپینگ (۲) Applying Pumping Lemma (2)

• به‌کارگیری لمای پمپینگ (۳) Applying Pumping Lemma (3)

• بسته بودن تحت عملیات مجموعه‌ای Closure Under Set Operations

• بسته بودن تحت معکوس و سایر عملیات Closure Under Reverse & Other Operations

زبان‌های مستقل از متن Context-Free Languages

• محدودیت‌های زبان‌های منظم Limitations of Regular Languages

• بازبینی تعریف گرامر Revisiting the Definition of Grammar

• مثال از زبان‌های تولید شده توسط CFG - ۱ Example of CFG’s Languages Generated by CFG - 1

• مثال از زبان‌های تولید شده توسط CFG - ۲ Example of CFG’s Languages Generated by CFG - 2

• مثال از زبان‌های تولید شده توسط CFG - ۳ Example of CFG’s Languages Generated by CFG - 3

• اشتقاق چپ‌ترین و راست‌ترین - ۱ Left Most and Right Most Derivation - 1

• زبان‌های مستقل از متن و کاربردهای آن‌ها Context-Free Languages and Applications

• مقدمه‌ای بر اتوماتای پشته‌ای (PDA) Introduction to Push-Down Automata

• عضویت در زبان‌ها، معادلات زبان‌ها و کاربردها Membership in Languages, Equivalence of Languages, Applications

• جمع‌بندی و خلاصه بخش Module Closure (Summary)

ابهام در گرامرهای مستقل از متن (CFG) Ambiguity in CFG

• معنای بررسی عضویت w در L What it Means to Verify if w ∈ L

• ضرورت گرامر برای تعریف بدون ابهام زبان‌ها Motivation for the Grammar to Specify Languages Unambiguously

• مثال ۱: گرامر مبهم Example 1 - Ambiguous Grammar

• مثال ۲: گرامر مبهم Example 2 - Ambiguous Grammar

• توضیح لمّا Explanation of Lemma

• مثال ۱: حذف تولیدات Example 1 - Eliminating Productions

• مثال ۲: حذف تولیدات Example 2 - Eliminating Productions

• فرم نرمال چیست و چرا به آن نیاز داریم؟ What is Normal Form? Why is Normal Form?

• بررسی انگیزه با یک مثال Motivation with an Example

• بیان لمای پمپینگ Pumping Lemma Statement

• مثال ۱ Example 1

• مثال ۲ Example 2

• مثال ۳ Example 3

• بسته بودن تحت عملیات اجتماع، الحاق و بسته کلین Closed Under Operations Union, Concatenation and Kleene-Closure

• عدم بسته بودن تحت اشتراک و متمم Not Closed Under Intersection and Complementation

• مثال‌ها Examples

• تعیین تهی یا نامتناهی بودن L(G) Deciding Whether L(G) is Empty and Infinite

• جمع‌بندی و خلاصه بخش Module Closure (Summary)

مقدمه‌ای بر تجزیه با روش Recursive Descent Introduction to Parsing with Recursive Descent Parsing

• مقدمه‌ای بر تجزیه (Parsing) Introduction to Parsing

• رویکردهای جستجوی اشتقاق Approaches to Look for Derivation

• نحوه نوشتن تجزیه‌گر Recursive Descent How to Write Recursive Descent Parser

• نوشتن یک تجزیه‌گر Recursive Descent به زبان C Writing a Recursive Descent Parser in C

• چالش‌های مثال گرامر عبارات Issues in the Expression Grammar Example

• بازنویسی گرامر: حذف بازگشتی چپ Rewriting the Grammar: Eliminate Left Recursion

• بازنویسی گرامر: فاکتورگیری چپ Rewriting the Grammar: Left Factoring

• بازنویسی گرامر: نمادهای غیرپایانی در گرامر Rewriting the Grammar: Non-Terminals in the Grammar

• تجزیه‌گر Recursive Descent برای گرامر عبارات بازنویسی شده Recursive Descent Parser for Rewritten Expressions Grammar

• نقاط ضعف تجزیه بازگشتی Drawbacks of Recursive Parsing

• خلاصه Summary

تجزیه LL(1) Parsing - LL(1)

• تجزیه LL(1) چیست؟ What is LL(1) Parsing?

• معرفی جدول تجزیه (پیش‌بین) و استفاده از آن برای تجزیه Introducing (Predictive) Parsing Table and Using it to Parse

• ساخت مجموعه‌های Nullable، First و Follow Construction of Nullable, First and Follow Sets

• الگوریتم ساخت Nullable، First و Follow Construction Algorithm - Nullable, First and Follow

• مثال ۱: Nullable، First و Follow Nullable, First and Follow - Example 1

• مثال ۲: Nullable، First و Follow Nullable, First and Follow - Example 2

• الگوریتم ساخت جدول Table Construction Algorithm

• تجزیه یک رشته با استفاده از جدول Parsing a String Using Table

• نمایش کد LL(1) در زبان C Code Demonstration for LL(1) in C

• مثال ۲ - جدول LL(1) Example 2 – LL(1) Table

• تضادها (Conflicts) در جدول تجزیه LL(1) چیستند؟ What are Conflicts in LL(1) Parsing Table?

• حل تضادها Resolving Conflicts

• تجزیه‌گرهای LL(2) و LL(k) LL(2) and LL(k) Parsers

• خلاصه Summary

تجزیه LR(0) و بررسی LR(k) Parsing - LR(0) and Illustration LR(k)

• نقاط ضعف تجزیه‌گرهای LL(k) What are the Weaknesses of LL(k) Parsers

• نمایش تجزیه‌گر Shift-Reduce Demonstration of Shift Reduce Parser

• نیاز به جدول تجزیه LR The Need of LR Parsing Table

• تجزیه LR(0) چیست؟ What is LR(0) Parsing?

• مثال: جدول تجزیه LR(0) برای تجزیه یک رشته Example: LR(0) Parsing Table to Parse a String

• ساخت جدول تجزیه LR(0) Constructing LR(0) Parsing Table

• تجزیه یک رشته با استفاده از LR(0) Parsing a String Using LR(0)

• تجزیه LR(1) و LR(k) چیست؟ What is LR(1) Parsing and LR(k) Parsing

• سلسله‌مراتب کلاس‌های گرامری شامل LL و LR Hierarchy of Grammar Classes Involving LL and LR

• خلاصه Summary

تجزیه سازه‌ای برای برچسب‌گذاری POS Constituency Parsing for POS Tagging

• معرفی برچسب‌گذاری POS: وظیفه و کاربردها Introducing POS Tagging - The Task and Applications

• رابطه CFG و برچسب‌گذاری POS CFG and POS Tagging

• برچسب‌گذاری POS به عنوان یک فرآیند تجزیه POS Tagging as Parsing

• مقدمه‌ای بر CSG (گرامرهای حساس به متن) Introduction to CSG

• مثال واقعی ۱ Real World Example 1

• مثال واقعی ۲ Real World Example 2

• کاربردها Applications

• مقدمه‌ای بر سلسله‌مراتب گرامرها Intro to Grammar Hierarchy

• مرور کلی Overview