ماشین محدود غیرمبهم
در نظریه ماشین‌ها ، ماشین محدود نامتناهی (UFA) یک نوع به خصوص از ماشین غیرقطعی محدود(NFA) میباشد. هر ماشین محدود قطعی ( DFA ) یک UFA هست اما برعکسش صادق نیست. DFA و UFA و NFA دقیقاً همان کلاس زبان رسمی را میشناسد. از یک طرف یک NFA میتواند به طور نمادین کوچکتر از یک DFA معادل باشد. از یک طرف بعضی از مشکلات میتواند روی DFA ها به راحتی حل شود و روی UFA ها نه.
برای مثال یک ماشین داده شده A را در نظر بگیرید ، یک ماشین A که میتواند مکمل A را بپذیرد میتواند در زمان خطی محاسبه شود که A یک DFA هست ، معلوم نیست که آیا میتوان آن را در زمان چندجمله‌ای برای UFA انجام داد. از این رو UFA ها ترکیبی از دنیاهای DFA و NFA هاست . در بعضی موارد آنها منجر به ماشین کوچکتر از DFA و الگوریتم‌های سریع تر از NFA میشوند.
یک NFA به طور رسمی با ۵- نشان داده میشود ، ( "A"=("Q", Σ, Δ, "q", "F" . برای هر کلمه "w = aa … a" یک UFA چنین است که یک NFA میباشد . در بیشتر موارد یک دنباله‌ای از حالات "r,r, …, r" در Q با شرایط زیر وجود دارد :
1. "r" = "q"
2. "r" ∈ Δ("r", "a"), for "i" = "0, …, n−1"
3. "r" ∈ "F".
به حروف آن شرایط این را بیان می‌کند که اگر w توسط A پذیرفته شود دقیقاً یک مسیر پذیرش وجود خواهد داشت که آن مسیری از حالت اولیه به حالت پایانی میباشد که توسط w برچسب زده شده است.
اگر L را مجموعه‌ای از کلمات {a,b} در نظر بگیریم که nامین حرف آخرشان a میباشد . ارقام یک DFA و یک UFA را نشان میدهد که این زبان را برای n=2 میپذیرد . DFA کمینه که L را میپذیرد 2 حالت دارد که یکی از آن زیر مجموعه‌ها {1…n} میباشد . یک UFA با n+1 حالت وجود دارد که L را میپذیرد : که nامین حرف آخر را حدس میزند و سپس تأیید میکند که فقط n-1 حرف مانده است . این در واقع یکنواخت است که فقط یک nامین حرف آخر وجود دارد.
۳ مشکل سخت برای NFA های عمومی که متعلق به PTIME برای DFA هست در نظر گرفته شده است.
در زمان چندجملهای قابل حل است یا اینکه یک زبان خودکار یک زیرمجموعه از یک زبان دیگر است.
اگر A و B دو ماشین باشند. (L(A و (L(B زبان‌هایی باشند که توسط این ماشین‌ها پذیرفته شده باشند. سپس ("L"("A")⊆"L"("B" اگر و فقط اگر (L(A∩ B)=L(A و جایی که A∩B ضرب دکارتی ماشین‌ها را نشان دهد ، که میتواند یکنواخت بودن را نیز ثابت کند . حال اگر (L(A∩B زیرمجموعه‌ای از (L(A با ساختن باشد ; بنابراین هر دو مجموعه مساوی است اگر و فقط اگر برای هر مقدار n∈ℕ تعداد طول کلمات n در (L(A∩B مساوی باشد با طول کلمات n در (L(A . میتوان ثابت کرد که کافیست تا هر n تا شماره حالات A و B چک شود .
تعداد طول کلمات n پذیرفته شده توسط ماشین میتواند با برنامه نویسی پویا توسط زمان چندجمله‌ای محاسبه شود که اثبات را به پایان میرساند.
مشکل جهانی بودن و همسان‌سازی که همچنین به PTIME هم تعلق دارد با کاهش گنجایش مشکل.
برای یک ماشین غیرقطعی محدود A با n حالت و m حرف الفبا ، زمان قابل قبول (O(nm میباشد که A غیر مبهم باشد. کافیست تا از الگوریتم تکرار نقطه ثابت استفاده کنیم تا مجموعه‌ای از حالت‌های جفت q و q' که دارای حرف a و w که به q و q' منجر میشود را محاسبه کنیم. ماشین غیرمبهم است اگر و فقط اگر هیچ جفتی نباشد که هر دو حالت آن را بپذیرند. اکثراً جفت‌های حالت (O(n2 وجود دارد و برای هر جفت m حرف وجود دارد تا الگوریتم تکرار نقطه ثابت را از سر بگیرد ، از این رو محاسبه زمان.مقاله اصلی :
ریاضیات اثبات میکند که هر UFA برای زبان نیاز به تعداد حالات مشخصی دارد که توسط Schmidt پیشگام شد. Leung اثبات میکند که یک DFA معادل به "n" حالت UFA نیاز به formula_1 حالت در بدترین حالت ممکن دارد و یک UFA معادل به "n" حالت NFA نیاز به formula_2 حالت دارد.
Jirásek ، Jirásková و Šebej تعداد حالات مورد نیاز برای نمایش عملیات اساسی در زبان را بررسی کردند. آنها به طور خاص ثابت کردند که برای هر n حالت UFA مکمل زبان که میپذیرد توسط UFA با formula_3 حالت میباشد.
برای الفبای یک حرفی Okhotin ثابت کرد که یک DFA معادل به یک UFA با "n" حالت نیاز به formula_4 حالت در بدترین مورد دارد.
ویکی‌پدیای انگلیسی :