تئوری محاسبات ( نظریه زبان ) : اتوماتا

یادگیری و بازی با DFA، NFA، DPDA، NPDA، LBA، ماشین تورینگ و زبان های رسمی.

عنوان اصلی : Theory of Computation(TOC) / Automata : Complete Pack - 2022

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

شروع : مقدمه :) :
زبان های رسمی
گرامر: تعریف
طبقه بندی گرامرها
Automata: تعریف
سلسله مراتب چامسکی: رابطه بین زبان ها، گرامرها و خودکارها
قدرت بیانی یا قدرت تشخیص خودکار.
اتوماتای ​​قطعی و غیر قطعی.
حالت های حافظه FA، PDA، TM.
اصول TOC ::
الفبا
رشته، طول، رشته خالی (اپسیلون).
زیر رشته، رشته فرعی بی اهمیت و غیر پیش پا افتاده و یادداشت.
پیوند و پسوند.
تعداد رشته های دارای Σ
n.
کلین کلوزور و بسته شدن مثبت.
زبان: تعریف، توجه.
زبان خالی، زبان غیر خالی، زبان متناهی و زبان بی نهایت.
زبان‌های معمولی:
مقدمه
انواع خودکارهای محدود
اتوماتای ​​محدود قطعی (DFA). :
زبان DFA ( L(M)).
حداقل DFA را بسازید: مثال 1
حداقل DFA را بسازید: مثال 2
حداقل DFA را بسازید: مثال 3
حداقل DFA را بسازید: مثال 4
نکات کلیدی: تعداد حالت ها برای شروع، پایان دادن به و زیر رشته.
حداقل DFA را بسازید: مثال 5
حداقل DFA را بسازید: مثال 6
ساخت نمونه های DFA حداقل:
مثال 7: L = { 1
2n | n >= 0}.
مثال 8 : L = { (10)
n | n >= 0}.
مثال 9: L = { 1
2n 0
m | m,n >= 1 }.
مثال 10: L = { 0
2 متر 1
3n | m,n >= 1 }.
مثال 11: L = { 0
متر 1
n | m,n >= 0 }.
مثال 12: L = { 0
متر 1
n | m >= 1، n >= 0 }.
مثال 13: L = { 0
متر 1
n | m + n = زوج }.
مثال 14: L = { 0
متر 1
n | m + n = فرد }.
اتوماتای ​​فشاری غیر قطعی (NFA). :
NFA : مقدمه.
زبان NFA و یادداشت.
مثال 1 : ساخت NFA برای زبان - L = { ε, 10, 01 }
مثال 2: ساخت NFA برای زبان - L = {0
n 1 0
m | m,n >= 1 }.
مثال 3: ساخت NFA برای زبان - L = {0
2n 1
m | m,n >= 1 }.
مثال 4: ساخت NFA برای زبان - L = {0
2 متر 1
3n | m,n >= 1 }.
مثال 5: ساخت NFA برای زبان - L = { (01)
2n | n >= 0}.
مثال 6: ساخت NFA برای زبان - L = شروع با 100.
مثال 7: ساخت NFA برای زبان - L = پایان دادن به 000.
مثال 8: ساخت NFA برای زبان - L = دارای زیر رشته 101.
مثال 9: ساخت NFA برای زبان - L =داشتن دو بیت آخر یکسان است.
مثال 10: ساخت NFA برای زبان - L = 4 بیت از سمت چپ 1 است.
مثال 11: ساخت NFA برای زبان - L = 5 بیت از سمت راست 1 است.
مثال 12: ساخت NFA برای L = با علامت یکسان شروع و پایان می یابد
مثال 13: ساخت NFA - L = با نمادهای مختلف شروع و پایان می یابد.
تبدیل NFA به DFA. :
الگوریتم
مثال 1: تبدیل.
مثال 2: تبدیل.
مثال 3: تبدیل.
ساخت زیر مجموعه.
مثال 4 برای ساخت DFA.
مثال 5 برای ساخت DFA.
تکمیل زبان معمولی. :
تعریف و در ادامه با مثال.
مثال 1
مثال 2
مثال 3
توجه: در L و L'.
مثال
عبارات منظم:
مثال 1: L = مجموعه ای از رشته های باینری که با 10 شروع می شوند.
مثال 2: L = مجموعه ای از رشته های باینری به 10 یا 01 ختم می شود.
مثال 3: L = مجموعه ای از رشته های باینری که در آن نماد 4 از انتهای چپ 1 است.
مثال 4: L = مجموعه ای از رشته های دوتایی به طول i) 3 ii) <= 3 iii) >= 3.
مثال 5: L = مجموعه ای از رشته های دوتایی به طول i) زوج ii) فرد iii) مضرب 3
مثال 6: L=تعداد 0ها i)2 است ii)<=2 ​​iii)>=2 iv) زوج v)فرد vi)ضرب 3
دستگاه خودکار (PDA) :
مثال 1: PDA برای L = a*
مثال 2: PDA برای L = ab*
مثال 3: PDA برای L = (ab)*a
مثال 4 : PDA برای L = { w ∈ (a+b)* | تعداد a = زوج }
مثال 5: PDA برای L = { w ∈ (a+b)* | |w| = 0 (Mod 3) }
مثال 6 : PDA برای L = { 0 m 1 n | m=n و m,n >=1 }.
مثال 7: PDA برای L = { 0 m 1 n | m <= n }.
مثال 8 : PDA برای L = { 0 m 1 n | m >= n }.
مثال 9 : PDA برای L = { 0 m 1 n | m ≠ n و m,n > 0}.
مثال 10: PDA برای L = { 0 m 1 n | m = 2n}.
مثال 11 : PDA برای L = { 0 m+n 1 n | m,n >= 1}.
مثال 12: PDA برای L = { 0 m 1 m+n | m,n >= 1 }.
مثال 13: PDA برای L = { 0 m 1 m+n 0 n | m,n >= 1 }.
مثال 14 : PDA برای L = { 0 m+n 0 m 1 n | m,n >=1 }.
مثال 15 : PDA برای L = { 0 m 1 n 0 m+n | m,n >= 1}.
مثال 17: PDA برای L = { a m b n c p | m = n یا n = p }.
مثال 18: PDA برای L = { a m b n c p | n = m + p }.
مثال 19: PDA برای L = { a m b n c n d m | m,n >= 1 }.
مثال 20: PDA برای L = { w x w R | w ∈ (a + b )* }.
مثال 21: PDA برای L = { w ∈(a+b)* | تعداد a = تعداد b }
ماشینگ تورینگ (TM):
مثال 1: ساخت ماشین تورینگ برای زبان L = {0 n 1 n | n >= 1}.
مثال 3: ساخت ماشین تورینگ برای رشته ها حاوی '101' است.
مثال 4: ماشین تورینگ را برای رشته‌ها بسازید که به "101" ختم می‌شود.
مثال 4.1: ماشین تورینگ ساده شده برای مثال 4.
مثال 5: ماشین تورینگ را برای جمع دو عدد واحد بسازید.
مثال 6: TM را برای تفریق تابع f(a-b) دو عدد واحد بسازید.
انحصاری: مثال 7 : ساخت TM برای L = {0 n 1 m 2 n+m | m,n >= 1}.
انحصاری: مثال 8 : ساخت TM برای L = {0 i 1 j 2 k | i*j=k & i,j >=1}.
انحصاری: مثال 9 : ساخت TM برای L = { ww | w ∈ {0،1} }.
مثال 9 (پسوند): TM را برای L = { wxw | w ∈ {0،1} }.
انحصاری: مثال 10: TM را بسازید که پالیندروم های با طول زوج را می پذیرد.
انحصاری: مثال 11: TM بسازید که پالیندروم های با طول فرد را بپذیرد.