یک زبان یک مجموعه(ی چندگانه) از رشته‌های دودویی (صفرویک) می‌باشد. یعنی ممکن است یک رشته بیش از یک بار در زبان آمده باشد. یک رشته پیشوند یک رشته‌ی دیگر است اگر و فقط اگر دقیقاً در ابتدای آن رشته ظاهر شده باشد. مثلاً رشته‌ی ‎۰۰۱۱‎ پیشوند رشته‌ی ‎۰۰۱۱۰۱‎ است. یک زبان، پیشوند-آزاد است اگر و فقط اگر هیچ عضو آن، پیشوند دیگری نباشد.

یک زبان داریم و در هر مرحله می‌توانیم یکی از اعضای آن را به رشته‌ی دیگری تغییر دهیم به شرطی که تعداد صفرهای رشته‌ی جدید، با تعداد صفرهای رشته‌ی قبلی برابر باشد و تعداد یک‌های رشته‌ی جدید نیز با تعداد یک‌های رشته‌ی قبلی برابر باشد.

الگوریتمی چندجمله‌ای ارائه کنید که بگوید آیا با تکرار این عمل، می‌توانیم این زبان را به یک زبان پیشوند-آزاد تبدیل کنیم یا نه.

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