به دنباله‌ای متناهی از حروف a و b که پشت سر هم قرار گرفته باشند یک کلمه می‌گوییم. مثلا bbab یا aaaaa هر کدام یک کلمه هستند. قاعده‌ای به نام «قاعده‌ی تحول» وجود دارد که طبق آن با داشتن کلمه‌ای مثل$ W$، اگر جایی در $ W$ ،ab مشاهده کردیم می‌توانیم آن را به bba تبدیل کنیم و به‌این‌ترتیب کلمه‌ی جدیدی مثل$ Wˊ$ به وجود بیاوریم. مثلا کلمه‌ی aabab را می‌توان با قاعده‌ی تحول به هر یک از کلمات abbaab یا aabbba تبدیل کرد (بر حسب این‌ که قاعده را روی اولین یا دومین abاجرا کنیم).

یک متخصص دستور زبان ادعا کرده است که «قاعده‌ی تحول توقف‌پذیر است.» یعنی اگر با هر کلمه‌ی دل خواه مثل $W_1$ شروع کنیم، با قاعده‌ی تحول آن را به کلمه‌ای مثل $W_2 $ تبدیل کنیم، سپس مجدداً با قاعده‌ی تحول $W_2$ را به کلمه‌ای مثل $W_3$ تبدیل کنیم، و همین‌طور ادامه دهیم، به‌جایی می‌رسیم که دیگر روی کلمه‌ی به‌دست‌آمده نمی‌توان قاعده‌ی تحول را اجرا کرد.

الف) درستی یا نادرستی این ادعا را ثبات کنید.

ب) قانون دیگری به نام «قانون تطوّر» وجود دارد که شبیه به قاعده‌ی تحول است با این تفاوت که اگر در کلمه‌ی $W$، رشته‌ی ab را مشاهده کردیم، می‌توانیم آن را به bbaa تبدیل کنیم. آیا قانون تطوّر توقف‌پذیر است؟

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