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

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

در نظریه ی اتوماتا , جایگشت اتوماتا یا ماشین خالص گروه یک ماشین تعیین‌پذیر حالات متناهی هستند به طوری که هر نماد ورودی جایگشت مجموعه ای از حالت هاست.به عبارت دیگر 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})$ تغییر میکند.