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

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

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

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

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

• مرجع: http://web.archive.org/web/20100216051324/http://www.cc.gatech.edu/classes/AY2008/cs3240_summer/hw4sol.pdf

• http://web.archive.org/web/20100216051324/

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

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

---

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

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