بطور
کلی مقدمات
نکته خاصی نداره ولی باید بر مفاهیم اولیه
مانند زبان.
رشته.
زیر
رشته.
پیشوند.
پسوند.
بستار.
گرامر.
اشتقاق.
هم
ارزی.
اتوماتا
و پذیرنده مسلط باشید!
فرق
dfa
و
nfa
تو
اینه که nfa
لاندا
هم میپذیره و در نتیجه تابع انتقال اون
به 2^Q
حالت
میره در حالی که توی dfa
تابع
انتقال به Q
حالت
میره.
پذیرنده
متناهی معین و نامعین هم ارزند.
تمام
زبانهای متناهی منظم هستند.
اگر
یک زبان منظم باشه اکثر زبانهایی که از
حذف یه بخش اون بدست میان هم منظم هستند.
مثل
اینکه یه تیکه از ته یا سر هر رشته حذف
کنیم یا فقط عناصر زوج یا فرد رشته ها رو
در نظر بگیریم و …
ماشین
متناهی که از روال کاهش بدست میاد کمینه
است.
ادغام
پذیر بودن یک رابطه هم ارزی است ولی ادغام
ناپذیر بودن هم ارزی نیست.
تو
ماشین میلی خروجی به انتقال بستگی داره(روی
یال نوشته میشه)
و
توی ماشین مور خروجی به حالت بستگی
داره(داخل
گره نوشته میشه)
ماشین
میلی و مور هم ارزند.
اگر
در ماشین میلی همه حالتها قابل تمایز
باشند آنگاه آن ماشین کمینه است.
چیزهایی
که باید از کتاب خوانده شود:
پذیرنده
متناهی معین dfa.
پذیرنده
متنهاهی نامعین nfa.
تبدیل
nfa
به
dfa.
ادغام
پذیری.
علامت
گذاری.
روال
کاهش.
ماشین
میلی و مور.
غیر
قابل تمایز k.
کمینه
سازی ماشین.
مترجم.
هیچ نظری موجود نیست:
ارسال یک نظر