فرض کنید یک ماشین در اختیار داریم که می‌تواند این سه کار را بر روی کارت‌هایی که بر روی هر یک از آن‌ها یک کلمه نوشته شده است انجام دهد:

• دو کارت که بر روی آن‌ها دو کلمه نوشته شده است را بگیرد و یک کارت تولید کند که بر روی آن این دو کلمه پشت سر هم نوشته شده‌اند. (برای مثال اگر بر روی کارت اول رشته‌ی aab و بر روی کارت دوم رشته‌ی bab نوشته شده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن aabbab نوشته شده است.)

• یک کارت که بر روی آن کلمه‌ی $S$ نوشته شده است را دریافت کند و در خروجی کارتی ایجاد کند که بر روی آن a$S$b نوشته شده است. (برای مثال اگر بر روی کارت ورودی کلمه‌ی aba نوشته شده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن کلمه‌یaabab نوشته شده است.)

• یک کارت که بر روی آن کلمه‌ی $S$ نوشته شده است را دریافت کند و در خروجی کارتی ایجاد کند که بر روی آن b$S$a نوشته شده است. (برای مثال اگر بر روی کارت ورودی هیچ کلمه‌ای نوشته نشده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن کلمه‌ی ba نوشته شده است.)

در ابتدا تعداد زیادی کارت که بر روی آن‌ها هیچ کلمه‌ای نوشته نشده است در اختیار ما قرار گرفته است.

۱) نشان دهید که با استفاده از این کارت‌ها و با این ماشین می‌توان کارتی را ایجاد کرد که بر روی آن کلمه‌ی abbaba نوشته شده باشد.

۲) ثابت کنید که با استفاده از این ماشین می‌توان هر کارتی که بر روی آن یک کلمه نوشته شده است را تولید کرد، اگر و فقط اگر این کلمه تنها از a و b تشکیل شده باشد و تعداد a های آن برابر با تعداد b های آن باشد.

• سوال بعد
• سوال قبل