حل تمرین نظریه محاسبات/فصل اول/حل تمرین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 برای تشخیص آن می باشد.

حل: