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

حل تمرین 1-10

تمرین

الف) نشان دهید که اگر M یک DFA برای تشخیص زبان B بوده و در این ماشین تمام حالت های پذیرش را به غیر پذیرش و تمام حالت های غیر پذیرش را به پذیرش تغییر دهیم، ماشین DFA به دست آمده مکمل زبان B را تشخیص می دهد. نتیجه بگیرید که زبان های منظم تحت عمل مکمل بسته هستند.

ب) با یک مثال نقض نشان دهید که اگر M یک NFA برای تشخیص زبان C بوده و در این ماشین تمام حالت های پذیرش را به غیر پذیرش و تمام حالت های غیر پذیرش را به پذیرش تغییر دهیم، ماشین NFA به دست آمده لزوماً مکمل زبان C را تشخیص نمی دهد. آیا کلاس زبان هایی که توسط NFA تشخیص داده می شوند، تحت عمل مکمل بسته هستند؟ پاسخ خود را توضیح دهید.

حل

الف)

هنگامیکه w Є B است، پس با آخرین عنصر w به وضعیت نهایی در M می رویم. و اگر w Є B نباشد، به وضعیتی غیر از وضعیت پذیرش در M که پذیش نیست می رویم. حال اگر وضعیت پذیرش به وضعیت غیر پذیرش و ما بقی وضعیت ها به وضعیت پذیرش تغییر یابند، dfa ی حاصل تمام رشته هایی را می پذیرد که عضو L نیستند(چون با عنصر آخر به یک وضعیت نهایی می روند) و از طرفی چون مسیر پیمایش هر رشته در dfa منحصر به فرد است پس عضومکمل B هستند.

پس با توجه به اینکه برای مکمل B یک dfa حاصل شد، مکمل B نیز منظم است و لذا زبان های منظم تحت عمل مکمل بسته هستند.

ب)

برای مثال M از دو حالت شروع و پایانی تشکیل شده باشد که باλ از شروع به پذیرش رفته باشیم.

کلاس زبان هایی که توسط NFA تشخیص داده می شوند، تحت عمل مکمل بسته هستند. زیرا متناظر همانnfa یک dfa وجود دارد.

نویسنده: امیررضا کرباسچیان