حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-35
ظاهر
حل تمرین1-35
تمرین
[ویرایش]مساله 1-34 را مطالعه کنید. فرض کنید L یک زبان بوده و x مجموعه ای از رشته ها باشد. x را زوج تمایز پذیر توسط L گویند اگر هر دورشته متفاوت عضو x تمایزپذیر توسط L باشد. شاخص L را بصورت حداکثر تعداد اجزا در هر مجموعه زوج تمایزپذیر توسط L تعریف می کنیم. شاخص L می تواند محدود یا نامحدود باشد.
الف- نشان دهید که اگر L با یک DFA با K حالت پذیرفته شود آنگاه شاخص L حداکثر K می باشد.
ب- نشان دهید که اگر L دارای شاخص محدود K باشد انگاه L را میتوان با یک DFA با K حالت تشخیص داد.
ج- نتیجه بگیرید که زبان L منظم است اگر و فقط اگر دارای شاخص محدود باشد. به عبارت دیگر شاخص ان اندازه کوچکترین DFA برای تشخیص آن می باشد.
حل: