حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-11

حل تمرین1-11

تمرین

با یک مثال نقض نشان دهید اثبات زیر برای بسته بودن کلاس زبان های منظم تحت بستار، صحیح نیست. اگر N1=(Q1, ∑ ,δ1,q1,F1) برای تشخیص زبان A1 باشد می توان ماشین راN1=(Q1, ∑ ,δ,q1,F) برای تشخیص زبان بستار A1 به صورت زیر ساخت.
الف – حالت های ماشین N همان حالات ماشین N1 است.
ب _ حالت شروع ماشین N همان حالت شروع ماشین N1 است .
پ _ حالت های پذیرش ماشین N همان حالات پذیرش ماشین N1 به علاوه حالت شروع است .
ت _ تابع انتقال δ به صورت زیر تعریف می شود :
δ(q,a) = δ1(q,a اگر q عضو F1 نباشد یا a تهی نباشد
δ(q,a) = δ1(q,a) اجتماع {q1} اگر q عضو F1 باشد یا a تهی باشد

حل

با این روش دستگاه جدید ε را که همیشه عضو بستار A است می‌پذیرد ولی ممکن است رشته های نا مطلوی دیگری را نیز بپذیرد که اشکال کار قرار دادن حالت شروع به عنوان حالت پذیرش است چون اگر زبان در حالت شروع باشد وبا یک ورودی دوباره به خودش برود (به عبارتی loop روی خودش کند) از آنجاییکه ما حالت شروع را به عنوان حالت پذیرش گرفتیم رشته ما مورد قبول می شود که نامطلوب است .
مثال : زبانی که تعداد فرد یک می پذیرد.

DFA این زبان دو حالت دارد : یکی حالت شروع( q0) و دیگری حالت پذیرش(q1).از حالت شروع با ورودی صفر به همان q0 و با ورودی یک به q1 می رویم. در q1 با امدن صفر به همان q1 و با آمدن یک به q0 می رویم. حالا اگر q0 را حالت پذیرش قرار دهیم زبان رشته هایی که به صفر ختم می‌شوند را نیز می پذیرد که نا مطلوب است.
برای حل این مشکل باید یک حالت شروع اضافه کنیم که حالت پذیرش نیز باشد و با ورودیε به حالت شروع قدیم (همان q0) برود. با این راه هم رشته ε بدون اضافه شدن هیچ رشته نا مطلوب دیگر به زبان اضافه می شود.