آموزش تئوری محاسبات: استاد DFA شوید

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

معرفی Introduction

• مقدمه ای بر نظریه محاسبات Introduction to Theory of Computation

• مجموعه ای از تمام رشته های ممکن بر روی یک الفبا Set of all Strings possible over an Alphabet

• رشته خالی در مقابل مجموعه خالی در مقابل زبان خالی Empty String vs Empty Set vs Empty Language

• تعداد رشته های ممکن بر روی یک الفبای به طول n Number of strings possible over an alphabet of length n

مقدمه ای بر اتوماتای ​​محدود قطعی (DFA) Introduction to Deterministic Finite Automata (DFA)

• DFA با مثال توضیح داده شده است DFA Explained with Example

• تغییر نام ایالت ها برای منطقی تر شدن آن Renaming of states to make it more logical

• DFA در مقابل حداقل DFA DFA vs Minimal DFA

• نمایندگی یک DFA Representation of a DFA

DFA بر اساس طول رشته DFA based on length of string

• حداقل DFA که رشته هایی با طول بیشتر از 2 را می پذیرد Minimal DFA that accepts strings of length greater than 2

• حداقل DFA که رشته هایی با طول کمتر از 3 را می پذیرد Minimal DFA that accepts strings of length less than 3

• DFA که رشته هایی به طول n را می پذیرد DFA that accepts strings of length n

• DFA که رشته هایی با طول حداقل n را می پذیرد DFA that accepts strings of length atleast n

• DFA که رشته هایی با طول حداکثر n را می پذیرد DFA that accepts strings of length atmost n

DFA بر اساس عملگر ماژول DFA based on modulo operator

• DFA که رشته هایی با طول زوج را می پذیرد DFA that accepts strings of even length

• چگونه تغییر حالت های نهایی می تواند زبان را تغییر دهد How changing final states can change the language

• DFA بر اساس طول رشته مدول 4 DFA based on length of string modulo 4

DFA بر اساس تعداد نمونه های یک نماد در یک رشته DFA based on number of instances of a symbol in a string

• DFA بر اساس تعداد a در یک رشته DFA based on number of a's in a string

• نکات مهم قابل توجه Important points to note

• نحوه تغییر DFA بسته به تغییر زبان How to change the DFA depending on language modification

DFA بر اساس تعداد نمونه های یک مدول نماد n DFA based on number of instances of a symbol modulo n

• DFA بر اساس تعداد مدول a's 3 DFA based on number of a's modulo 3

• DFA بر اساس تعداد مدول a's 5 DFA based on number of a's modulo 5

DFA بر اساس محصول دکارتی DFA based on cartesian product

• DFA 1 در محصول دکارتی DFA 1 on cartesian product

• DFA 2 در محصول دکارتی DFA 2 on cartesian product

DFA بر اساس تفسیر یک رشته به عنوان یک عدد باینری DFA based on Interpretation of a string as a binary number

• DFA بر اساس پذیرش رشته های باینری که بر 2 بخش پذیر هستند DFA based on accepting binary strings which are divisible by 2

• DFA بر اساس پذیرش رشته های باینری که بر 4 بخش پذیر است DFA based on accepting binary strings which are divisible by 4

• DFA بر اساس پذیرش رشته های باینری که بر 5 بخش پذیر است DFA based on accepting binary strings which are divisible by 5

DFA بر اساس نماد شروع، نماد پایان و رشته فرعی DFA based on start symbol, end symbol and substring

• DFA بر اساس نماد شروع DFA based on start symbol

• DFA بر اساس رشته فرعی DFA based on substring

• DFA بر اساس نمادهای شروع DFA based on start symbols

• DFA بر اساس نماد پایان DFA based on end symbol

• DFA بر اساس نمادهای پایانی DFA based on end symbols

• DFA بر اساس نمادهای پایانی DFA based on end symbols

• DFA بر اساس نمادهای پایانی DFA based on end symbols

• DFA بر اساس رشته فرعی DFA based on substring

• DFA بر اساس رشته فرعی DFA based on substring

• DFA بر اساس نماد شروع و نماد پایان DFA based on start symbol and end symbol

• DFA بر اساس نماد شروع و نماد پایان DFA based on start symbol and end symbol

• DFA بر اساس نماد شروع و پایان DFA based on start and end symbol

• DFA که رشته هایی را می پذیرد که با نمادهای مختلف شروع و پایان می یابند DFA which accepts strings which starts and ends with different symbols

• DFA که رشته هایی را می پذیرد که با یک علامت شروع و پایان می یابند DFA which accepts strings which starts and ends with the same symbol

مکمل Complementation

• مکمل یک زبان Complementation of a language

• مثال 1 در مورد تکمیل یک زبان Example 1 on Complementation of a language

• مثال 2 در مورد مکمل یک زبان Example 2 on complementation of a language

• DFA بر اساس نماد زیر DFA based on following symbol

• تکمیل یک DFA Complementation of a DFA

• ساخت DFA از طریق تکنیک مکمل Constructing DFA through complementation technique

• DFA بر اساس نماد زیر DFA based on following symbol

• DFA بر اساس رشته فرعی DFA based on substring

• DFA بر اساس نماد زیر DFA based on following symbol

• DFA بر اساس نماد زیر DFA based on following symbol

DFAهای پیشرفته Advanced DFA's

• مشکل 1 Problem 1

• مشکل 2 Problem 2

• مشکل 3 Problem 3

• مشکل 4 Problem 4

• مشکل 5 Problem 5

• مشکل 6 Problem 6

• مسئله 7 Problem 7

• مسئله 8 Problem 8

• مسئله 9 Problem 9

• مسئله 10 Problem 10

• مسئله 11 Problem 11

عملیات بین زبانها Operations between languages

• اتحاد بین زبانها Union between languages

• مشکل در عملیات اتحادیه Problem on Union Operation

• مشکل در عملیات اتحادیه Problem on Union Operation

• الحاق بین زبانها Concatenation between languages

• مشکل در عملیات الحاق Problem on Concatenation Operation

• معکوس کردن یک زبان Reversal of a language

• مسئله Problem

پاداش: چگونه ادامه دهید Bonus : How to proceed further

• پاداش: چگونه ادامه دهید Bonus : How to proceed further