مسئله کلمات جداکننده

در علوم نظری رایانه، مسئله کلمات جداکننده، مسئله یافتن کوچک‌ترین ماشین متناهی قطعی است که در دو رشته داده شده رفتار متفاوتی دارد، به این معنی که یکی از دو رشته را می‌پذیرد و رشته دیگر را رد می‌کند. یافتن تعداد حالات این ماشین، یک مسئله باز است و در بدترین حالت، تابعی از طول رشته‌های ورودی است.

مثال 
دو رشته ۰۰۱۰ و ۱۰۰۰ می‌توانند توسط یک ماشین سه حالته از یکدیگر متمایز شوند که در آن انتقال از حالت شروع به دو حالت مختلف می‌رود، که هر دو پایانی هستند به این معنا که انتقال‌های بعدی از این دو حالت همیشه به همان حالت اولیه بازمی‌گردد. حالت این ماشین اولین نماد رشته ورودی را ثبت می‌کند. اگر یکی از دو حالت پایانی قبول و دیگری رد باشد، ماشین تنها یکی از رشته‌های ۰۰۱۰ و ۱۰۰۰ را می‌پذیرد. با این حال، این دو رشته را نمی‌توان با هیچ ماشینی با کمتر از سه حالت متمایز کرد.

ساده‌سازی مفروضات 
برای اثبات کرانه‌های این مسئله، بدون از دست دادن کلیت، فرض می‌شود که ورودی‌ها، رشته‌هایی روی یک الفبای دو حرفی هستند؛ زیرا، اگر دو رشته در یک الفبای بزرگ‌تر با هم متفاوت باشند، یک هم‌ریختی رشته‌ای وجود دارد که آنها را به رشته‌هایی باینری با طول یکسان، نگاشت می‌کند که در این نگاشت، هر دو رشته همچنان با هم متفاوت هستند. هر ماشینی که این دو رشته باینری را متمایز می‌کند، می‌تواند به ماشینی تبدیل شود که رشته‌های اصلی را بدون هیچ افزایشی در تعداد حالت‌ها متمایز کند.

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

تاریخچه و کرانه‌ها 
مسئله محدود کردن اندازه ماشینی که دو رشته داده شده را از هم متمایز می‌کند، برای اولین بار توسط  فرموله شد، که نشان دادند اندازه ماشین همیشه زیرخطی است. بعدها،  بهترین کران بالایی شناخته شده، ، در اندازه ماشینی که ممکن است مورد نیاز باشد را اثبات کرد. این مقدار توسط  به  بهبود یافت.

جفت ورودی‌هایی وجود دارند که هر دو رشته‌های باینری به طول  هستند و هر ماشینی که ورودی‌ها را متمایز می‌کند باید اندازه  باشد. بستن شکاف بین این کران پایین و کران بالایی رابسون همچنان یک مسئله باز است. جفری شالیت جایزه ۱۰۰ پوندی بریتانیا را برای هر بهبودی در حد بالایی رابسون در نظر گرفته‌است.

حالت‌های خاص 
چندین مورد خاص از مسئله جداکننده کلمات، با استفاده از چند حالت مشخص، قابل حل شناخته شده‌است:
 اگر دو کلمه باینری دارای تعداد متفاوتی صفر یا یک باشند، آنگاه می‌توان آنها را با شمارش مدول وزن‌های همینگ آن‌ها با اندازه لگاریتمی عددی اول، با استفاده از تعداد لگاریتمی حالت‌ها از یکدیگر متمایز کرد. به‌طور کلی، اگر یک الگوی طول ، متفاوت بار در دو کلمه ظاهر شود، می‌توان‌آنها را با استفاده از تعداد  حالت از یکدیگر متمایز کرد.
 اگر دو کلمه باینری در اولین یا آخرین  با یکدیگر متفاوت باشند، می‌توان آنها را با استفاده از  حالت از یکدیگر متمایز کرد. این نشان می‌دهد که تقریباً همه جفت‌های کلمات باینری را می‌توان با تعداد لگاریتمی از حالت‌ها از یکدیگر متمایز کرد، زیرا تنها درصد کمی از جفت‌ها در موقعیت‌های  اولیه خود با هم تفاوتی ندارند.
 اگر دو کلمه باینری فاصله همینگ  را داشته باشند، عدد اول  با  و یک موقعیت  که در آن دو رشته متفاوت هستند، به طوری که  برابر مدول  با موقعیت هیچ تفاوت دیگری نیست وجود دارد. با محاسبه زوج و فردی نمادهای ورودی در موقعیت‌های همخوان با  modulo ، می‌توان کلمات را با استفاده از ماشینی با  حالت از هم دیگر تمایز داد.

منابع 

ماشین متناهی