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

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

مقدمه‌ای بر ماشین‌های متناهی Introduction to Finite Automata

• مقدمه‌ای بر نظریه ماشین‌ها Introduction to Automata Theory

• مفاهیم بنیادین نظریه ماشین‌ها و سلسله مراتب چامسکی Fundamental Concepts of Automata Theory and Chomsky Hierarchy

• مقدمه‌ای بر ماشین‌های متناهی (FA) Introduction to Finite Automata (FA)

• ماشین‌های متناهی (FA): پذیرش، نمایش‌های ساختاری و پیچیدگی Finite Automata (FA): Acceptance, Structural Representations and Complexity

• ماشین‌های متناهی قطعی (DFA) Deterministic Finite Automata (DFA)

• ماشین‌های متناهی غیر قطعی (NFA) Nondeterministic Finite Automata (NFA)

• معادل بودن NFA و DFA Equivalence of NFA and DFA

ماشین‌های متناهی با انتقال اپسیلون (NFA-ϵ) Finite Automata with Epsilon Transitions (NFA-ϵ)

• ماشین‌های متناهی با انتقال اپسیلون (NFA-ϵ) Finite Automata with Epsilon Transitions (NFA-ϵ)

• معادل بودن NFA با و بدون حرکات ϵ (حذف انتقال‌های ϵ) Equivalence of NFA with and without ϵ-moves (Eliminating ϵ-transitions)

• تبدیل NFA-ϵ (با اپسیلون) به DFA Conversion of NFA-ϵ (with epsilon) to DFA

ماشین‌های متناهی با خروجی: ماشین‌های مور و میلی Finite Automata with Output: Moore and Mealy Machines

• مقدمه‌ای بر ماشین‌های مور و میلی Introduction to Moore and Mealy machines

• تبدیل ماشین میلی به ماشین مور Conversion of Mealy machine to Moore machine

• تبدیل ماشین مور به ماشین میلی Conversion of Moore machine to Mealy machine

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

• مقدمه‌ای بر عبارات منظم Introduction to Regular Expressions

• عبارات منظم: قوانین جبری و کاربردها Regular Expressions: Algebraic Laws & Applications

• تبدیل عبارت منظم به ماشین متناهی (FA) Conversion of Regular Expression to Finite Automata (FA)

• تبدیل ماشین متناهی (FA) به عبارت منظم Conversion of Finite Automata (FA) to Regular Expression

لم تزریق و خواص بستاری زبان‌های منظم Pumping Lemma and Closure Properties of Regular Languages

• لم تزریق برای مجموعه‌های منظم / زبان‌های منظم Pumping Lemma for Regular Sets / Regular Languages

• خواص بستاری و تصمیم‌گیری برای مجموعه‌های منظم / زبان‌های منظم Closure Properties & Decision Properties for Regular Sets / Regular Languages

معادل بودن و کمینه‌سازی ماشین‌های متناهی (FAs) Equivalence and Minimization of Finite Automatons (FAs)

• معادل بودن بین دو ماشین حالت متناهی (FSM) / ماشین متناهی (FA) Equivalence between two Finite State Machines (FSMs) / Finite Automatons (FAs)

• کمینه‌سازی ماشین‌های متناهی قطعی (DFA) Minimization of Deterministic Finite Automata (DFA)

• ساخت DFA کمینه شده Construction of Minimized DFA

گرامرهای منظم و ماشین‌های متناهی (FA) Regular Grammars and Finite Automata (FA)

• مقدمه‌ای بر گرامرهای منظم Introduction to Regular Grammars

• گرامرهای منظم و ماشین‌های متناهی (FA) Regular Grammars and Finite Automata (FA)

گرامرهای مستقل از متن Context-Free Grammars

• مقدمه‌ای بر گرامرهای مستقل از متن (CFG's) Introduction to Context-free Grammars (CFG's)

• گرامرهای مستقل از متن (CFG's): درخت تجزیه/درخت اشتقاق و کاربردهای CFGها Context-free Grammars (CFG's): Parse Tree/Derivation Tree & Applications of CFGs

• گرامرهای مستقل از متن (CFG's): ابهام Context free Grammars (CFG's): Ambiguity

• گرامرهای مستقل از متن (CFG's): رفع ابهام Context free Grammars (CFG's): Eliminating Ambiguity

ماشین‌های پشته‌ای Push Down Automata

• مقدمه‌ای بر ماشین‌های پشته‌ای (PDA) Introduction to Pushdown Automata (PDA)

• ماشین‌های پشته‌ای (PDA)-پذیرش زبان‌ها توسط حالت نهایی و پشته خالی Pushdown Automata (PDA)-Acceptance of Languages by Final State & Empty Stack

• طراحی PDA برای CFL قسمت-1 Design of PDA for CFL part-1

• طراحی PDA برای CFL قسمت-2 Design of PDA for CFL part-2

• معادل بودن PDAها و CFGها: تبدیل CFG به PDA Equivalence of PDA's and CFG's: Conversion of CFG to PDA

• معادل بودن PDAها و CFGها: تبدیل CFG به PDA Equivalence of PDA's and CFG's: Conversion of CFG to PDA

• ماشین‌های پشته‌ای قطعی (DPDA) Deterministic Pushdown Automata (DPDA)

فرم‌های نرمال برای گرامرهای مستقل از متن Normal Forms for Context- Free Grammars

• فرم‌های نرمال برای CFGها: حذف نمادهای بی‌فایده و تولیدات بی‌فایده Normal Forms for CFGs: Removing useless symbols & useless productions

• فرم‌های نرمال برای CFG: حذف تولیدات پوچ و تولیدات واحد Normal forms for CFG: Removing Null Productions & Unit Productions

• فرم‌های نرمال برای CFG: فرم نرمال چامسکی (CNF) Normal forms for CFG: Chomsky Normal Form (CNF)

• فرم‌های نرمال برای CFG: فرم نرمال گریباک (GNF) Normal Forms for CFG- Greibach Normal Form (GNF)

لم تزریق و خواص بستاری زبان‌های مستقل از متن Pumping Lemma and Closure Properties of Context-Free Languages

• لم تزریق برای زبان‌های مستقل از متن Pumping Lemma for Context-Free Languages

• خواص بستاری زبان‌های مستقل از متن Closure Properties of Context-Free Languages

ماشین تورینگ (TM) Turing Machine (TM)

• مقدمه‌ای بر ماشین تورینگ (TM) Introduction to Turing Machine (TM)

• خواص بستاری زبان‌های بازگشتی و بازگشتی شمارا Closure properties of Recursive and Recursively Enumerable Languages

• طراحی ماشین تورینگ برای زبان‌ها Design of Turing Machine for Languages

• انواع ماشین تورینگ (TM) Types of Turing Machine (TM)

• ماشین تورینگ (TM)-توابع قابل محاسبه Turing Machine (TM)- Computable Functions

تصمیم‌ناپذیری Undecidability

• تصمیم‌ناپذیری-زبان بازگشتی شمارا و ماشین تورینگ Undecidability-Recursively Enumerable Language and Turing Machine

• تصمیم‌ناپذیری-مسئله تطابق پست (PCP) و سایر مسائل تصمیم‌ناپذیر Undecidability-Post's Correspondence Problem (PCP) & Other Undecidable Problems

• سلسله مراتب چامسکی زبان‌های صوری و تشخیص‌دهنده‌ها Chomsky Hierarchy of Formal Languages and Recognizers

مثال‌های حل شده Solved Example Problems

• تبدیل عبارت منظم به ماشین متناهی-مثال مسئله Conversion of Regular Expression to Finite Automata-Example problem

• ساخت ماشین متناهی که حداقل دو 0 یا 1 متوالی را می‌پذیرد Construction of Finite Automata that accepts atleast two consecutive 0's or 1's

• ساخت DFA که تعداد فردی 0 و 1 را می‌پذیرد Construction of DFA that accepts Odd number of 0's and 1's

• سخنرانی 53. مسئله زنده - تبدیل NFA با حرکات ϵ به NFA بدون حرکات ϵ Lecture 53. Live Problem -Conversion of NFA with ϵ-moves to NFA without ϵ-moves

• سخنرانی-54. مسئله زنده - تبدیل NFA به DFA (روش-1) Lecture-54. Live Problem - Conversion of NFA to DFA (Method-1)

• سخنرانی-55. مسئله زنده - تبدیل NFA به DFA (روش-2) Lecture-55. Live Problem - Conversion of NFA to DFA (Method-2)

• سخنرانی-56. مسئله زنده - تبدیل NFA-ϵ به DFA مستقیم Lecture-56. Live Problem - Conversion of NFA-ϵ to Direct DFA

• سخنرانی-57. مسئله زنده - تبدیل ماشین مور به ماشین میلی Lecture-57. Live Problem - Conversion of Moore machine to Mealy Machine

• سخنرانی-58. مسئله زنده - تبدیل ماشین میلی به ماشین مور Lecture-58. Live Problem - Conversion of Mealy Machine to Moore Machine

• سخنرانی-59. مسئله زنده - ساخت DFA از عبارت منظم Lecture-59. Live Problem - Construction of DFA from Regular Expression

آزمون تمرینی Practice Test

• آزمون تمرینی Practice Test