جایگشت اتوماتا

در نظریهٔ اتوماتا (به انگلیسی: Automata theory)، جایگشت اتوماتا یا ماشین خالص گروه یک ماشین تعیین‌پذیر حالات متناهی هستند به طوری که هر نماد ورودی جایگشت مجموعه‌ای از حالت هاست. به عبارت دیگر DFA A را ممکن است با چند تایی (Q, Σ, δ, q0, F) نمایش دهند که Q مجموعهٔ وضعیت‌های ماشین، Σ مجموعهٔ نمادهای ورودی،δ تابع انتقال که وضعیت q و نماد ورودی x را می‌گیرد و q را به وضعیت جدید (δ(q,x انتقال می‌دهد. q0 وضعیت شروع ماشین است؛ و F مجموعهٔ وضعیت‌های پذیرفته شده (همچنین وضعیت پایانی) ماشین است. A یک جایگشت اتوماتاست اگر و تنها اگر برای هر دو وضعیت مجزای qi و qj در Q و هر ورودی x در Σ داشته باشیم

 (δ(qi,x) ≠ δ(qj,x

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

نرم‌افزار

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