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