مرجع دانلود پاورپوینت های درسی

حجم فایل : 1.0 MB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 61
بنام خدا نظریه زبان ها و ماشین ها فصل اول- زبان های منظم و ماشین های حالت متناهی پاییز 86 عناوین مورد بحث ماشین های حالت متناهی
عدم قطعیت
عبارات منظم
زبان های نامنظم
لم پامپینگ پاییز 86 ماشین حالت متناهی ساده ترین مدل محاسباتی کامپیوترها، یک ماشین حالت متناهی (finite Automaton یا finite State Machine) است.
مناسب برای مدلسازی کامپیوترهایی با حافظه بسیار محدود
در سیستم های نهفته (Embedded Systems) استفاده چنین ماشین هایی بسیار رایج است.
زنجیره های مارکوفی (Markov Chains) همتای احتمالی ماشین های حالت متناهی هستند.
این مدل ها در پردازش گفتار و OCR برای تشخیص الگوهای موجود در داده ها کاربرد دارند.
پاییز 86 یک مثال ساده کنترلر یک در خودکار پاییز 86 یک مثال ساده - ادامه نمودار حالت



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

می گوییم ماشین M زبان A را تشخیص می دهد (می پذیرد) پاییز 86 بازگشت به مثال قبل پاییز 86 مثال M4 تمام رشته هایی از a و b را می پذیرد که ابتدا و انتهای آن یکسان است. پاییز 86 تعریف صوری پذیرش پاییز 86 زبان منظم پاییز 86 مثال پاییز 86 طراحی یک ماشین حالت متناهی خودتان را به جای ماشین تصور کنید.

یک ماشین حالت متناهی که رشته های شامل 001 را بپذیرد.
حالات ممکن عبارتند از:
پاییز 86 اعمال روی زبان های منظم پاییز 86 بسته بودن مجموعه زبان های منظم نسبت به اجتماع پاییز 86 اثبات پاییز 86 بسته بودن مجموعه زبان های منظم نسبت به الحاق برای اثبات این ویژگی نیاز به تعریف مفهوم عدم قطعیت داریم.
پاییز 86 تفاوت میان NFA و DFA پاییز 86 مقایسه مفهوم پذیرش در NFA و DFA پاییز 86 مثال پاییز 86 تعریف صوری ماشین حالت متناهی غیرقطعی(NFA) پاییز 86 مثال پاییز 86 هم ارزی NFAها و DFAها ایده اثبات: تبدیل NFA به DFAی که رفتار آن را شبیه سازی می کند.
اگر NFAی دارای k حالت باشد، برای شبیه سازی آن توسط یک DFA به k2 حالت نیاز خواهیم داشت. پاییز 86 اثبات ابتدا بدون در نظر گرفتن گذارهای ε، ماشین جدید را می سازیم. پاییز 86 در نظر گرفتن گذارهای ε پاییز 86 در نظر گرفتن گذارهای ε پاییز 86 نتیجه پاییز 86 مثال پاییز 86 مثال - ادامه حذف حالات غیر قابل دسترسی پاییز 86 اثبات قضایای بسته بودن با استفاده از NFA پاییز 86 اثبات بسته بودن نسبت به اجتماع پاییز 86 اثبات- ادامه پاییز 86 اثبات بسته بودن نسبت به الحاق پاییز 86 اثبات- ادامه پاییز 86 اثبات بسته بودن نسبت به * پاییز 86 اثبات- ادامه پاییز 86 عبارات منظم آیا این تعریف...