مقدمه ای بر تئوری خودکار، زبان ها و محاسبات

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

مقدمه ای بر تئوری خودکار، زبان ها و محاسبات Introduction to Automata Theory, Languages and Computation

• معرفی این دوره Introduction to this course

• مقدمه ای بر اتومات - زبان ها - سلسله مراتب چامسکی Introduction to Automata - Languages - Chomsky Hierarchy

• زبان های رسمی: رشته ها، زبان ها Formal Languages: Strings, Languages

• سلسله مراتب چامسکی Chomsky Hierarchy

• مقدمه Introduction

مقدمه ای بر Finite Automata Introduction to Finite Automata

• مقدمه ای بر Finite Automata Introduction to Finite Automata

• DFA و NFA DFA and NFA

• DFA - تابع انتقال گسترده و پذیرش زبان DFA - Extended Transition Function and Language Acceptance

• NFA - تابع انتقال گسترده و پذیرش زبان NFA - Extended Transition Function and Language Acceptance

• نمونه هایی از DFA و NFA - زبان رشته ها Examples of DFA and NFA - language of strings

• مثال DFA برای مکمل هر زبان Example DFA for complement of any language

• خودکار محدود با حرکت های یورو Finite Automaton with €- moves

• نمایش محدود: عبارات منظم (RE) Finite Representation : Regular Expressions (RE)

• پمپاژ لم برای RE Pumping Lemma for RE

• خودکارهای محدود Finite Automata

هم ارزی در میان Automata محدود Equivalence among Finite Automata

• معادل NFA، DFA، NFA با €- حرکت و RE Equivalence of NFA, DFA, NFA with €- moves and RE

• کار و مثال برای روش ساخت زیر مجموعه Working and examples for Subset construction Method

• NFA به DFA با استفاده از روش ساخت زیر مجموعه تنبل NFA to DFA using Lazy subset construction Method

• روش ساخت تامسون برای RE تا Ꜫ-NFA Thomson's Construction Method for RE to Ꜫ-NFA

• بیان منظم به DFA Regular Expression to DFA

• نمونه های حل شده برای RE تا DFA Solved Examples for RE to DFA

• به حداقل رساندن DFA Minimization of DFA

• اپسیلون NFA به NFA Epsilon NFA to NFA

• DFA به RE (روش فرمول) DFA to RE (Formula Method)

• نمونه های حل شده برای DFA به RE (روش فرمول) Solved Examples for DFA to RE (Formula Method)

• مثال های حل شده برای حالت های DFA تا RE 3 (روش فرمول) Solved Examples for DFA to RE 3 states (Formula method)

• DFA به RE (روش حذف حالت) DFA to RE (State Elimination Method)

• اتوماتای ​​محدود - مثال 1 - سوال سناریو Finite Automata - Example 1 - Scenario Question

• خودکارهای محدود - مثال 2 - سوال مبتنی بر سناریو Finite Automata - Example 2 - Scenario based question

• Automata محدود - مثال 3 - سوال مبتنی بر سناریو برای ساخت DFA Finite Automata - Example 3 - Scenario based question for DFA construction

• معادل سازی خودکارهای محدود Equivalence of Finite Automata

اتومات با خروجی Automata With Output

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

• مثال ماشین مور و سه روش نمایش Moore machine Example and Three ways of representation

• مثال ماشین Mealy و سه روش نمایش Mealy machine Example and Three ways of representation

• ماشین مور به ماشین Mealy Moore Machine to Mealy Machine

• دستگاه Mealy به دستگاه مور Mealy machine to Moore machine

Context Free Garmmar Context Free Garmmar

• مقدمه، انواع گرامر و بازنمایی Introduction, Types of Grammar and Representation

• گرامر آزاد زمینه (CFG) و زبان ها Context Free Grammar (CFG) and Languages

• مثال 1: ساخت CFG Example 1: CFG construction

• مثال 2: ساخت CFG Example 2: CFG construction

• مثال 3: ساخت CFG Example 3: CFG construction

• اشتقاق، درخت تجزیه و ابهام Derivation, Parse tree and Ambiguity

• ساده سازی CFG - حذف نمادهای بی فایده Simplification of CFG - Elimination of Useless Symbols

• ساده سازی CFG - حذف تولیدات پوچ Simplification of CFG - Elimination of Null productions

• ساده سازی CFG - حذف تولیدات واحد Simplification of CFG - Elimination of Unit productions

• CFG به فرم معمولی چامسکی (CNF) CFG to Chomsky Normal Form (CNF)

• مثال مبتنی بر سناریو برای CNF Scenario based example for CNF

• مثال های حل شده - CFG به CNF Solved Examples - CFG to CNF

• فرم طبیعی CFG به گریباخ CFG to Greibach Normal form

• مثال های حل شده - CFG به GNF Solved Examples - CFG to GNF

• مثال های حل شده - CNF به GNF Solved Examples - CNF to GNF

• سناریو GNF Scenario GNF

• مثال 1 - سوال مبتنی بر سناریو برای CNF و GNF Example 1 - Scenario based question for CNF and GNF

• گرامر آزاد زمینه Context Free Grammar

فشار به پایین خودکار Push Down Automata

• مقدمه ای بر Push Down Automata Introduction to Push Down Automata

• مشکل در PDA {a^nb^n/n>1} Problem in PDA {a^nb^n/n>1}

• مشکل در PDA {a^n b^ m/n,m>=1} دو مشکل (n>m) و (m>n) Problem in PDA {a^n b^ m/n,m>=1} two problems (n>m) and (m>n)

• مشکل در PDA { WCW^R/w={a,b}*} Problem in PDA { WCW^R/ w={a,b}*}

• PDA غیر قطعی {Palindrome of a String} Non-Deterministic PDA {Palindrome of a string}

• CFG (Context Free Grammar) به PDA (Push Down Automata) CFG (Context Free Grammar) to PDA (Push Down Automata)

• PDA (Push Down Automata) به CFG (Context Free Grammar) PDA (Push Down Automata) to CFG (Context Free Grammar)

• Pumping Lemma برای CFG Pumping Lemma for CFG

• سوال مبتنی بر سناریو در CFG و PDA Scenario based question in CFG and PDA

• فشار به پایین خودکار Push Down Automata

ماشین تورینگ Turing Machine

• مقدمه ای بر ماشین تورینگ، توضیحات لحظه ای Introduction to Turing Machine, Instantaneous Description

• نمایش ماشین تورینگ Turing Machine Representations

• ماشین تورینگ برای زبان معمولی Turing Machine for Regular Language

• ماشین تورینگ برای زبان آزاد متن Turing Machine for Context Free Language

• TM برای L={a^n b^n c^n/n>=0} TM for L={a^n b^n c^n / n>=0}

• TM برای پالیندروم یک رشته بر روی الفبای a،b TM for palindrome of a string over alphabet a,b

• TM برای تفریق مناسب TM for proper subtraction

• TM برای ضرب TM for Multiplication

• تغییرات TM Modifications of TM

• شبیه سازی ماشین تورینگ Simulation of Turing Machine

• ماشین تورینگ Turing Machine

مشکلات حل شده اضافی در Automata محدود، Push Down Automata و Turing Machine Extra solved problems in Finite Automata, Push Down Automata and Turing Machine

• مثال 1: زبان معمولی - ساخت DFA، PDA و TM Example 1 : Regular Language - construction of DFA, PDA and TM

• مثال 2: زبان آزاد متن - ساخت PDA و TM Example 2 : Context Free Language - Construction of PDA and TM

• مثال 3: مشکل ماشین تورینگ Example 3 : Turing Machine problem

• مثال 4: ماشین تورینگ برای مکمل 1 Example 4 : Turing Machine for 1's Complement

• مثال 5: سوال مبتنی بر سناریو در ماشین تورینگ Example 5 : scenario based question in Turing Machine

• مثال 6: سوال مبتنی بر سناریو در ماشین تورینگ Example 6 : scenario based question in Turing Machine

• مثال 7: سوال مبتنی بر سناریو در ماشین تورینگ Example 7 : scenario based question in Turing Machine

• مثال 8: سوال مبتنی بر سناریو در PDA و CFG Example 8 : scenario based question in PDA and CFG

تصمیم پذیری و تصمیم ناپذیری Decidability and Undecidability

• تصمیم پذیری و تصمیم ناپذیری Decidability and Undecidability

مشکلات کلاس P و کلاس NP Class P and Class NP problems

• سوال مبتنی بر سناریو در PCP Scenario based question in PCP