پاورپوینت ظریه زبان ها و ماشین ها

بخشی از پاورپوینت

اسلاید 1 :

نظریه زبان ها و ماشین ها

اسلاید 2 :

عناوین مورد بحث
ماشین های حالت متناهی
عدم قطعیت
عبارات منظم
زبان های نامنظم
لم پامپینگ

اسلاید 3 :

ماشین حالت متناهی
ساده ترین مدل محاسباتی کامپیوترها، یک ماشین حالت متناهی (finite Automaton یا finite State Machine) است.
مناسب برای مدلسازی کامپیوترهایی با حافظه بسیار محدود
در سیستم های نهفته (Embedded Systems) استفاده چنین ماشین هایی بسیار رایج است.
زنجیره های مارکوفی (Markov Chains) همتای احتمالی ماشین های حالت متناهی هستند.
این مدل ها در پردازش گفتار و OCR برای تشخیص الگوهای موجود در داده ها کاربرد دارند.

اسلاید 4 :

یک مثال ساده
کنترلر یک در خودکار

اسلاید 5 :

یک مثال ساده - ادامه
نمودار حالت
جدول گذار(انتقال حالت)

اسلاید 6 :

تعریف ریاضی

اسلاید 7 :

مثال

اسلاید 8 :

زبان یک ماشین حالت متناهی
نتیجه پردازش هر رشته از علائم ورودی توسط یک ماشین حالت متناهی پذیرش(accept) یا رد(reject) است.
اگر A مجموعه تمام رشته هایی باشد که ماشین M می پذیرد، A را زبان ماشین M می گوییم و می نویسیم: L(M) = A

می گوییم ماشین M زبان A را تشخیص می دهد (می پذیرد)

اسلاید 9 :

بازگشت به مثال قبل

اسلاید 10 :

مثال
M4 تمام رشته هایی از a و b را می پذیرد که ابتدا و انتهای آن یکسان است.

اسلاید 11 :

تعریف صوری پذیرش

اسلاید 12 :

زبان منظم

اسلاید 13 :

مثال

اسلاید 14 :

طراحی یک ماشین حالت متناهی
خودتان را به جای ماشین تصور کنید.

یک ماشین حالت متناهی که رشته های شامل 001 را بپذیرد.
حالات ممکن عبارتند از:

اسلاید 15 :

اعمال روی زبان های منظم

اسلاید 16 :

بسته بودن مجموعه زبان های منظم نسبت به اجتماع

اسلاید 17 :

اثبات

اسلاید 18 :

بسته بودن مجموعه زبان های منظم نسبت به الحاق
برای اثبات این ویژگی نیاز به تعریف مفهوم عدم قطعیت داریم.

اسلاید 19 :

تفاوت میان NFA و DFA

اسلاید 20 :

مقایسه مفهوم پذیرش در NFA و DFA