ماشین محدود غیرمبهم

در نظریه ماشین‌ها ، ماشین محدود نامتناهی (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 = a₁a₂ … a_n یک UFA چنین است که یک NFA میباشد . در بیشتر موارد یک دنباله‌ای از حالات r₀,r₁, …, r_n در Q با شرایط زیر وجود دارد :

1. r₀ = q₀

2. r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, …, n−1

3. r_n ∈ 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امین حرف آخر وجود دارد.

گنجایش و مشکلات مربوط

۳ مشکل سخت PSPACE برای NFA های عمومی که متعلق به PTIME برای DFA هست در نظر گرفته شده است.

گنجایش

در زمان چندجملهای قابل حل است یا اینکه یک زبان خودکار یک زیرمجموعه از یک زبان دیگر است.

ماشین قطعی (DFA) برای زبان L برای n=2

ماشین محدود نامتناهی(UFA) برای زبان L برای n=2

طرح اثبات پذیرش

اگر 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(n²m میباشد که A غیر مبهم باشد.

طرح اثبات غیرمبهم

کافیست تا از الگوریتم تکرار نقطه ثابت استفاده کنیم تا مجموعه‌ای از حالت‌های جفت q و q' که دارای حرف a و w که به q و q' منجر میشود را محاسبه کنیم. ماشین غیرمبهم است اگر و فقط اگر هیچ جفتی نباشد که هر دو حالت آن را بپذیرند. اکثراً جفت‌های حالت (O(n2 وجود دارد و برای هر جفت m حرف وجود دارد تا الگوریتم تکرار نقطه ثابت را از سر بگیرد ، از این رو محاسبه زمان.

برخی خواص

1. ضرب دکارتی دو UFA یک UFA میباشد .
2. مفهوم عدم همبستگی به مبدل‌های حالت و ماشین‌های وزنی محدود است. اگر یک مبدل حالت محدود T غیرمبهم باشد ، سپس هر حرف ورودی به T حداکثر به یک کلمه خروجی ارتباط میابد. اگر ماشین وزنی A غیرمبهم باشد ، سپس مجموعه وزن نیاز ندارد تا semiring باشد در عوض کافیست یک monoid را در نظر بگیرید در واقع اکثراً یک مسیر پذیرش وجود دارد.

پیچیدگی حالت

مقاله اصلی : State Complexity

ریاضیات اثبات میکند که هر UFA برای زبان نیاز به تعداد حالات مشخصی دارد که توسط Schmidt پیشگام شد. Leung اثبات میکند که یک DFA معادل به n حالت UFA نیاز به $2^{n}$ حالت در بدترین حالت ممکن دارد و یک UFA معادل به n حالت NFA نیاز به $2^{n}-1$ حالت دارد.

Jirásek ، Jirásková و Šebej تعداد حالات مورد نیاز برای نمایش عملیات اساسی در زبان را بررسی کردند. آنها به طور خاص ثابت کردند که برای هر n حالت UFA مکمل زبان که میپذیرد توسط UFA با ${\displaystyle O(2^{0.79n})}$ حالت میباشد.

برای الفبای یک حرفی Okhotin ثابت کرد که یک DFA معادل به یک UFA با n حالت نیاز به ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$ حالت در بدترین مورد دارد.

منابع

ویکی‌پدیای انگلیسی : Unambiguous finite automaton