ماشین جایگشت

در نظریه اتوماتا، ماشین جایگشت یا ماشین pure-group یک ماشین تعیین‌پذیر حالات متناهی است. به طوری که هر نماد ورودی جایگشت مجموعه‌ای از حالت هاست. به عبارت دیگر DFA A را ممکن است با چند تایی (Q, Σ, δ, q₀, F) نمایش دهند که Q مجموعهٔ وضعیت‌های ماشین، Σ مجموعهٔ نمادهای ورودی، δ تابع انتقال که وضعیت q و نماد ورودی x را می‌گیرد و q را به وضعیت جدید (δ(q,x انتقال می‌دهد. q₀ وضعیت شروع ماشین است؛ و F مجموعهٔ وضعیت‌های پذیرفته شده (همچنین وضعیت پایانی) ماشین است. A یک جایگشت اتوماتاست اگر و تنها اگر برای هر دو وضعیت مجزای q_i و q_j در Q و هر ورودی x در Σ داشته باشیم: (δ(q_i,x) ≠ δ(q_j,x

یک زبان صوری را p-منظم گویند اگر به وسیلهٔ یک ماشین جایگشت پذیرفته شود. به طور مثال مجموعهٔ رشته‌های به طول زوج به فرم زبان p-منظم هستند:این مجموعه شاید به وسیلهٔ یک جایگشت اتوماتا با دو وضعیت که در هر انتقال هر وضعیت با وضعیت دیگر جایگزین می‌شود، پذیرفته شود.

نرم‌افزار

زبان‌های pure-group اولین خانواده جالب توجه زبان‌های منظم بودند که مشکل ارتفاع ستاره برای آنها به اثبات رسیده بود تا محاسبه پذیر شوند. مشکل ریاضی دیگری برای زبان‌های منظم مشکل حروف جداکننده است که برای اندازهٔ کوچکترین DFA که بین دو کلمه به طول حداکثر n به صورت پذیرفتن یک لغت و رد لغت دیگر تمایز ایجاد می‌کند، می‌پرسد. کران بالای شناخته شده در حالت کلی $O(n^{2/5}(\log n)^{3/5})$ است این مشکل بعداً مورد بررسی قرار گرفت و کران بالای شناخته شده به $O(n^{1/2})$ تغییر یافت.