آلة محدودة ذاتية التحقق

في نظرية الأوتوماتا ، تُعدّ الأوتوماتا المحدودة ذاتية التحقق ( SVFA ) نوعًا خاصًا من الأوتوماتا المحدودة غير الحتمية (NFA) ذات نوع متناظر من عدم الحتمية، وقد قدّمها هرومكوفيتش وشنيتجر. ^{[ 1 ]} عمومًا، في عدم الحتمية ذاتية التحقق، ينتهي كل مسار حسابي بأحد الإجابات الثلاث الممكنة: نعم ، لا ، لا أعرف . بالنسبة لكل سلسلة إدخال، لا يمكن لمسارين أن يُعطيا إجابتين متناقضتين، أي أنه لا يمكن الحصول على إجابتي نعم ولا في نفس الإدخال. يجب أن يُعطي مسار واحد على الأقل إجابة نعم أو لا ، وإذا كانت الإجابة نعم، تُعتبر السلسلة مقبولة. تقبل الأوتوماتا المحدودة ذاتية التحقق نفس فئة اللغات التي تقبلها الأوتوماتا المحدودة الحتمية (DFA) والأوتوماتا المحدودة غير الحتمية (NFA) ، ولكنها تختلف عنها في تعقيد الحالة .

يُمثَّل SVFA رسميًا بواسطة مجموعة سداسية ، A = ( Q _, Σ , Δ, q₀ _, Fa , _{Fr )} ، بحيث تكون ( Q , Σ , _Δ , q₀ , Fa ) عبارة عن NFA ، و _Fa و Fr _{مجموعتان} جزئيتان منفصلتان من Q. لكل كلمة w = a₁ _a₂ … aₙ _، تكون العملية الحسابية عبارة عن سلسلة من الحالات r₀ _{, r₁ ,} … , rn _في Q مع الشروط التالية:

1. r ₀ = q ₀
2. r _i+1 ∈ Δ( r _i , a _i+1 ), for i = 0, …, n−1 .

إذا كان r_{_n} ∈ F _{_a} فإن الحساب يكون مقبولاً، وإذا كان r_{_n} ∈ F _{_r} فإن الحساب يكون رافضاً. ويشترط أن يكون لكل w حساب واحد على الأقل مقبولاً أو حساب واحد على الأقل رافضاً، ولكن ليس كلاهما.

كل آلة حتمية محدودة (DFA) هي آلة حتمية محدودة ذات حالة ثابتة (SVFA)، ولكن ليس العكس. أثبتت جيراسكوڤا وبيغيزيني ^{[ 2 ]} أنه لكل آلة حتمية محدودة ذات حالة ثابتة مكونة من n حالة، توجد آلة حتمية محدودة مكافئة لها.${\displaystyle g(n)=\Theta (3^{n/3})}$علاوة على ذلك، لكل عدد صحيح موجب n ، يوجد SVFA ذو n حالة بحيث يكون لـ DFA المكافئ الأدنى بالضبط${\displaystyle g(n)}$الولايات.

وقد توصلت جيراسكوڤا وزملاؤها إلى نتائج أخرى تتعلق بتعقيد حالة SVFA. ^{[ 3 ] [ 4 ]}