پاورپوینت نظریه زبان ها و ماشین ها فصل اول- زبان های منظم و ماشین های حالت متناهی

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

اسلاید 1 :

نظریه زبان ها و ماشین ها
فصل اول- زبان های منظم و ماشین های حالت متناهی

اسلاید 2 :

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

اسلاید 3 :

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

اسلاید 4 :

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



جدول گذار(انتقال حالت)

اسلاید 5 :

تعریف ریاضی

اسلاید 7 :

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

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

اسلاید 8 :

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

اسلاید 9 :

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

اسلاید 10 :

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

اسلاید 11 :

زبان منظم

اسلاید 13 :

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

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

اسلاید 14 :

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

اسلاید 15 :

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

اسلاید 16 :

اثبات

اسلاید 17 :

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

اسلاید 18 :

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

اسلاید 19 :

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