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

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

برای اینکه نشان دهیم زبانی مستقل از متن است باید PDA یاCFG آن را نشان دهیم.البته چون وسط رشته مشخص نمی شود یک زبان نامعین است.

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

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

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 symbol and pop the stack. Repeat until the stack is empty.

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

6. Nondeterministically jump to either Step 5 or Step 7.

7. Reject if the current symbol is the same as the symbol remembered in Step 3.

8. Read the next input symbol and pop the stack. Repeat until the stack is empty.

9. Accept if the input is empty

یک CFG برای این زبان: S->UV|VU

U->0U0|1U0|0U1|1U1|0

V->0V0|1V0|0V1|1V1|1