حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۲۶

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

حل تمرین ۲-۲۶ از ویرایش اول کتاب (در ویرایش دوم کتاب شماره این مساله ۲-۲۲ است)

فرض کنید {C = {x#y|x,y {0,1}, x ≠ y باشد.

نشان دهید که C مستقل از متن است.

برای این زبان می‌توان یک آتوماتای پشته‌ای نامعین طراحی کرد، پس مستقل از متن است.

این آتوماتا به شکل زیر است

1. Read the next input symbol, and push a 1 onto the stack.

2. Nondeterministically jump to either Step 1 or Step 3.

3. Remember the current input symbol in the finite control.

4. Read the next input symbols until # is read.

5. Read the next symbol, and pop the stack.

6. If the stack is empty, go to Step 7, else go to Step 5.

7. Accept if the current input symbol is different from the symbol remembered in Step 3. Otherwise reject.


رسم آتوماتا

مرجع http://web.archive.org/web/20120813071853/http://www.cs.uni-salzburg.at/~ck/wiki/uploads/TCSSummer2005.ProVe/Theory.pdf

Sipser2-26.jpg



گرامرهایی که به شکل زیر نوشته شوند غلط هستند

S → A1T | B0T | G | H

A → CAC | 0T#

B → CBC | 1T#

C → 0 | 1

T → 0T | 1T | ε

G → CGC | CG | C#

H → CHC | HC | #C