الأوتوماتون المحدود غير الحتمي

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 119 صور
الموسوعة الحرة
NFA لـ (0 | 1) *  1  (0 | 1) 3. تحتوي DFA لتلك اللغة على 16 حالة على الأقل .

في نظرية الأوتوماتا ، تُسمى الآلة ذات الحالة المحدودة بالأوتوماتا المحدودة الحتمية (DFA)، إذا

  • يتم تحديد كل انتقال من انتقالاتها بشكل فريد من خلال حالة المصدر ورمز الإدخال، و
  • يلزم قراءة رمز الإدخال لكل انتقال حالة.

لا تخضع الآلة المحدودة غير الحتمية (NFA)، أو آلة الحالة المحدودة غير الحتمية، لهذه القيود. على وجه الخصوص، كل آلة محدودة حتمية (DFA) هي أيضًا آلة محدودة غير حتمية. يُستخدم مصطلح NFA أحيانًا بمعنى أضيق ، للإشارة إلى آلة محدودة غير حتمية ليست آلة محدودة حتمية، ولكن ليس في هذا المقال.

باستخدام خوارزمية بناء المجموعات الفرعية ، يمكن ترجمة كل آلة حالة نهائية غير قطعية (NFA) إلى آلة حالة نهائية قطعية (DFA) مكافئة؛ أي آلة حالة نهائية قطعية تتعرف على نفس اللغة الرسمية . [ 1 ] ومثل آلات الحالة النهائية القطعية، فإن آلات الحالة النهائية غير القطعية لا تتعرف إلا على اللغات المنتظمة .

طُرحت الآلات غير القطعية المحدودة (NFAs) عام 1959 على يد مايكل أو. رابين ودانا سكوت ، [ 2 ] اللذين أثبتا أيضًا تكافؤها مع الآلات القطعية المحدودة (DFAs). تُستخدم الآلات غير القطعية المحدودة في تنفيذ التعابير النمطية : خوارزمية تومسون هي خوارزمية لتحويل التعبير النمطي إلى آلة غير قطعية محدودة قادرة على إجراء مطابقة الأنماط بكفاءة على السلاسل النصية. في المقابل، يمكن استخدام خوارزمية كلين لتحويل آلة غير قطعية محدودة إلى تعبير نمطي (يكون حجمه عادةً أُسّيًا في الآلة المدخلة).

تم تعميم الأوتوماتا غير القطعية (NFAs) بطرق متعددة، مثل الأوتوماتا غير القطعية ذات الحركات ε ، والمحولات ذات الحالة المحدودة ، وأوتوماتا الدفع لأسفل ، والأوتوماتا المتناوبة ، وأوتوماتا ω ، والأوتوماتا الاحتمالية . إلى جانب الأوتوماتا القطعية (DFAs)، تشمل الحالات الخاصة الأخرى المعروفة للأوتوماتا غير القطعية الأوتوماتا القطعية غير المبهمة (UFA) والأوتوماتا القطعية ذاتية التحقق (SVFA).

مقدمة غير رسمية

توجد طريقتان متكافئتان على الأقل لوصف سلوك آلة الحالة المحدودة غير القطعية (NFA). تعتمد الطريقة الأولى على عدم الحتمية في اسم الآلة. فلكل رمز إدخال، تنتقل الآلة إلى حالة جديدة حتى يتم استهلاك جميع رموز الإدخال. في كل خطوة، "تختار" الآلة بشكل غير حتمي أحد الانتقالات المتاحة. إذا وُجدت سلسلة اختيارات ناجحة واحدة على الأقل، أي سلسلة تؤدي إلى حالة قبول بعد استهلاك الإدخال بالكامل، يتم قبول الإدخال. وإلا، أي إذا لم تتمكن أي سلسلة اختيارات من استهلاك جميع الإدخال [ 3 ] والوصول إلى حالة قبول، يتم رفض الإدخال. [ 4 ] [ 5 ] : 319 [ 6 ]

في الطريقة الثانية، تستهلك آلة الحالة المحدودة غير القطعية (NFA) سلسلة من رموز الإدخال، رمزًا تلو الآخر. في كل خطوة، عندما يكون هناك انتقالان أو أكثر قابلان للتطبيق، فإنها "تستنسخ" نفسها إلى عدد مناسب من النسخ، تتبع كل نسخة انتقالًا مختلفًا. إذا لم يكن هناك انتقال قابل للتطبيق، فإن النسخة الحالية تكون في طريق مسدود، و"تتوقف". إذا كانت أي من النسخ، بعد استهلاك الإدخال بالكامل، في حالة قبول، يتم قبول الإدخال، وإلا يتم رفضه. [ 4 ] [ 7 ] [ 6 ]

التعريف الرسمي

للحصول على مقدمة أكثر بساطة للتعريف الرسمي، انظر نظرية الأوتوماتا .

آلة

يتم تمثيل NFA رسميًا بواسطة مجموعة من 5 عناصر ، (سؤال،Σ،دلتا،q0،F){\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}، ويتألف من

  • مجموعة محدودة من الحالاتسؤال{\displaystyle Q}،
  • مجموعة محدودة من رموز الإدخال تسمى الأبجديةΣ{\displaystyle \Sigma }،
  • دالة انتقاليةدلتا{\displaystyle \delta } :سؤال×Σ→P(سؤال){\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}،
  • حالة أولية (أو حالة بداية)q0∈سؤال{\displaystyle q_{0}\in Q}، و
  • مجموعة من الحالات المقبولة (أو النهائية)F⊆سؤال{\displaystyle F\subseteq Q}.

هنا،P(سؤال){\displaystyle {\mathcal {P}}(Q)}يشير إلى مجموعة القوى لـسؤال{\displaystyle Q}.

لغة معترف بها

بالنظر إلى NFAم=(سؤال،Σ،دلتا،q0،F){\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}لغتها المعترف بها يُرمز لها بـل(م){\displaystyle L(M)}، ويُعرَّف بأنه مجموعة جميع السلاسل المكونة من حروف الأبجديةΣ{\displaystyle \Sigma }التي تقبلهام{\displaystyle M}.

وبالتوافق بشكل عام مع التفسيرات غير الرسمية المذكورة أعلاه ، توجد عدة تعريفات رسمية مكافئة للسلسلةw=أ1أ2...أن{\displaystyle w=a_{1}a_{2}...a_{n}}قبولها من قبلم{\displaystyle M}:

  • w{\displaystyle w}يُقبل إذا كانت سلسلة من الحالات،ر0،ر1،...،رن{\displaystyle r_{0},r_{1},...,r_{n}}، موجود فيسؤال{\displaystyle Q}بحيث:
    1. ر0=q0{\displaystyle r_{0}=q_{0}}
    2. رأنا+1∈دلتا(رأنا،أأنا+1){\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}، لأنا=0،...،ن-1{\displaystyle i=0,\ldots ,n-1}
    3. رن∈F{\displaystyle r_{n}\in F}.
بعبارة أخرى، ينص الشرط الأول على أن الآلة تبدأ في حالة البدءq0{\displaystyle q_{0}}الشرط الثاني ينص على أنه بالنظر إلى كل حرف من السلسلةw{\displaystyle w}ستنتقل الآلة من حالة إلى أخرى وفقًا لدالة الانتقال.دلتا{\displaystyle \delta }ينص الشرط الأخير على أن الجهاز يقبلw{\displaystyle w}إذا كان الإدخال الأخير لـw{\displaystyle w}يتسبب ذلك في توقف الآلة في إحدى حالات القبول. لكيw{\displaystyle w}يتم قبولها من قبلم{\displaystyle M}ليس من الضروري أن تنتهي كل سلسلة حالات بحالة قبول، يكفي أن تنتهي إحداها. وإلا، أي إذا كان من المستحيل تمامًا الانتقال منq0{\displaystyle q_{0}}إلى ولاية منF{\displaystyle F}باتباعw{\displaystyle w}يقال إن الآلة ترفض السلسلة. مجموعة السلاسلم{\displaystyle M}يقبل اللغة المعترف بها بواسطةم{\displaystyle M}ويُرمز إلى هذه اللغة بـل(م){\displaystyle L(M)}. [ 5 ] : 320 [ 8 ]
  • بدلاً عن ذلك،w{\displaystyle w}يتم قبولها إذادلتا*(q0،w)∩F≠∅{\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }، أيندلتا*:سؤال×Σ*→P(سؤال){\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}يتم تعريفها بشكل متكرر بواسطة:
    1. دلتا*(ر،ε)={ر}{\displaystyle \delta ^{*}(r,\varepsilon )=\{r\}}أينε{\displaystyle \varepsilon }هي سلسلة فارغة، و
    2. دلتا*(ر،xأ)=⋃ر′∈دلتا*(ر،x)دلتا(ر′،أ){\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}للجميعx∈Σ*،أ∈Σ{\displaystyle x\in \Sigma ^{*},a\in \Sigma }.
بالكلمات،دلتا*(ر،x){\displaystyle \delta ^{*}(r,x)}هي مجموعة جميع الولايات التي يمكن الوصول إليها من الولايةر{\displaystyle r}عن طريق استهلاك السلسلةx{\displaystyle x}الخيطw{\displaystyle w}يُقبل ذلك إذا كانت هناك دولة تقبل ذلك فيF{\displaystyle F}يمكن الوصول إليها من حالة البدايةq0{\displaystyle q_{0}}عن طريق الاستهلاكw{\displaystyle w}[ 9 ] [ 10 ]​

الحالة الابتدائية

يستخدم تعريف الأوتوماتون أعلاه حالة ابتدائية واحدة ، وهو أمر غير ضروري. في بعض الأحيان، تُعرَّف الأوتوماتونات غير القطعية (NFAs) بمجموعة من الحالات الابتدائية. توجد طريقة سهلة لتحويل الأوتوماتون غير القطعي ذي الحالات الابتدائية المتعددة إلى أوتوماتون غير قطعي ذي حالة ابتدائية واحدة، مما يوفر تدوينًا ملائمًا.

التماثل

التشاكل​φ{\displaystyle \varphi }من آلة(سؤال،Σ،دلتا،q0،F){\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}إلى آلة(سؤال′،Σ،دلتا′،q0′،F′){\displaystyle (Q',\Sigma ,\delta ',q'_{0},F')}هو تطبيق تقابليφ:سؤال→سؤال′{\displaystyle \varphi :Q\to Q'}بحيث

  • φ(q0)=q0′{\displaystyle \varphi (q_{0})=q'_{0}}،
  • q∈F{\displaystyle q\in F}إذا، وفقط إذا،φ(q)∈F′{\displaystyle \varphi (q)\in F'}لكلq∈سؤال{\displaystyle q\in Q}، و
  • ر∈دلتا(q،أ){\displaystyle r\in \delta (q,a)}إذا، وفقط إذا،φ(ر)∈دلتا′(φ(q)،أ){\displaystyle \varphi (r)\in \delta '(\varphi (q),a)}لكلq،ر∈سؤال{\displaystyle q,r\in Q}وأ∈Σ{\displaystyle a\in \Sigma }.

بشكل بديهي، يكون جهازان آليان متماثلين إذا كانا يشتركان في نفس الأبجدية ويمكن الحصول على أحدهما عن طريق إعادة تسمية حالات الآخر بشكل منهجي.

مثال

مخطط الحالة لـ M. إنه ليس حتميًا لأنه في الحالة p، يمكن أن تؤدي قراءة 1 إلى p أو إلى q .
جميع التسلسلات الممكنة للحرف M على سلسلة الإدخال "10"
جميع التسلسلات الممكنة لـ M على سلسلة الإدخال "1011". تسمية القوس: رمز الإدخال، تسمية العقدة : الحالة، الأخضر : حالة البداية، الأحمر : حالة (حالات) القبول.
مدخل
تسلسل الحالة
1011
1صq؟
2صصصq؟
3صصصصq

تحدد الآلة M التالية ، المزودة بأبجدية ثنائية، ما إذا كان المدخل ينتهي بالرقم 1.م=({ص،q}،{0،1}،دلتا،ص،{q}){\displaystyle M=(\{p,q\},\{0,1\},\delta ,p,\{q\})}حيث دالة الانتقالدلتا{\displaystyle \delta }يمكن تعريفها بواسطة جدول انتقال الحالة هذا (انظر الصورة العلوية اليسرى):

ولايةمدخل01ص{ص}{ص،q}q∅∅{\displaystyle {\begin{array}{|c|cc|}{\bcancel {{}_{\text{State}}\quad {}^{\text{Input}}}}&0&1\\\hline p&\{p\}&\{p,q\}\\q&\emptyset &\emptyset \end{array}}}

منذ المجموعةدلتا(ص،1){\displaystyle \delta (p,1)}إذا احتوت M على أكثر من حالة واحدة، فهي غير حتمية. ويمكن وصف لغة M باللغة المنتظمة المعطاة بالتعبير النمطي(0|1)*1 .

تظهر جميع تسلسلات الحالة الممكنة لسلسلة الإدخال "1011" في الصورة السفلية.

يقبل النظام M السلسلة لأن إحدى سلاسل الحالات تحقق التعريف المذكور أعلاه؛ ولا يهم أن السلاسل الأخرى لا تحققه. يمكن تفسير الصورة بطريقتين:

  • فيما يتعلق بتفسير "المسار المحظوظ" المذكور أعلاه ، فإن كل مسار في الصورة يمثل سلسلة من خيارات M.
  • فيما يتعلق بتفسير "الاستنساخ"، يُظهر كل عمود رأسي جميع نسخ M في وقت معين، وتشير الأسهم المتعددة المنبثقة من عقدة إلى الاستنساخ، وتشير العقدة بدون أسهم منبثقة إلى "موت" النسخة المستنسخة.

إن إمكانية قراءة الصورة نفسها بطريقتين تشير أيضاً إلى تكافؤ التفسيرين المذكورين أعلاه.

  • بالنظر إلى التعريف الرسمي الأول المذكور أعلاه ، يُقبل الرقم "1011" لأنه عند قراءته قد يجتاز M تسلسل الحالة⟨ر0،ر1،ر2،ر3،ر4⟩=⟨ص،ص،ص،ص،q⟩{\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }، وهو ما يفي بالشروط من 1 إلى 3.
  • أما فيما يتعلق بالتعريف الرسمي الثاني، فإن الحسابات التصاعدية تُظهر أندلتا*(ص،ε)={ص}{\displaystyle \delta ^{*}(p,\varepsilon )=\{p\}}، لذلكدلتا*(ص،1)=دلتا(ص،1)={ص،q}{\displaystyle \delta ^{*}(p,1)=\delta (p,1)=\{p,q\}}، لذلكدلتا*(ص،10)=دلتا(ص،0)∪دلتا(q،0)={ص}∪{}{\displaystyle \delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}}، لذلكدلتا*(ص،101)=دلتا(ص،1)={ص،q}{\displaystyle \delta ^{*}(p,101)=\delta (p,1)=\{p,q\}}وبالتاليدلتا*(ص،1011)=دلتا(ص،1)∪دلتا(q،1)={ص،q}∪{}{\displaystyle \delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}}؛ لأن تلك المجموعة ليست منفصلة عن{q}{\displaystyle \{q\}}، يتم قبول السلسلة "1011".

في المقابل، يرفض النظام M السلسلة "10" (جميع تسلسلات الحالات الممكنة لهذا المدخل موضحة في الصورة العلوية اليمنى)، إذ لا توجد طريقة للوصول إلى حالة القبول الوحيدة، q ، بقراءة الرمز 0 الأخير. مع أن q يمكن الوصول إليها بعد استهلاك الرمز "1" الأولي، إلا أن هذا لا يعني قبول المدخل "10"، بل يعني قبول سلسلة المدخل "1".

مكافئ لـ DFA

يمكن اعتبار الأوتوماتون المحدود الحتمي (DFA) نوعًا خاصًا من الأوتوماتون غير المحدود (NFA)، حيث يكون لكل حالة ورمز دالة انتقالية واحدة فقط. وبالتالي، من الواضح أن كل لغة رسمية يمكن التعرف عليها بواسطة DFA يمكن التعرف عليها بواسطة NFA.

في المقابل، لكل آلة حالة نهائية غير قطعية (NFA)، توجد آلة حالة نهائية قطعية (DFA) تتعرف على نفس اللغة الرسمية. ويمكن بناء آلة الحالة النهائية القطعية باستخدام بناء مجموعة القوى .

تُظهر هذه النتيجة أن الآلات غير القطعية المحدودة (NFAs)، على الرغم من مرونتها الإضافية، لا تستطيع التعرف على اللغات التي لا تستطيع بعض الآلات القطعية المحدودة (DFAs) التعرف عليها. كما أنها مهمة عمليًا لتحويل الآلات غير القطعية المحدودة الأسهل في الإنشاء إلى آلات قطعية محدودة أكثر كفاءة في التنفيذ. مع ذلك، إذا كانت الآلة غير القطعية المحدودة تحتوي على n حالة، فقد تحتوي الآلة القطعية المحدودة الناتجة على ما يصل إلى 2^ n حالة، مما يجعل عملية الإنشاء غير عملية في بعض الأحيان بالنسبة للآلات غير القطعية المحدودة الكبيرة.

NFA مع حركات إبسيلون

الأوتوماتون المحدود غير الحتمي ذو الحركات ε (NFA-ε) هو تعميم إضافي للأوتوماتون المحدود غير الحتمي. في هذا النوع من الأوتوماتون، تُعرَّف دالة الانتقال أيضًا على السلسلة الفارغة ε. يُسمى الانتقال الذي لا يستهلك رمزًا من رموز الإدخال انتقال ε، ويُمثَّل في مخططات الحالة بسهم يحمل علامة "ε". توفر انتقالات ε طريقة ملائمة لنمذجة الأنظمة التي لا تُعرف حالاتها الحالية بدقة؛ أي، إذا كنا ننمذج نظامًا ولم يكن واضحًا ما إذا كانت الحالة الحالية (بعد معالجة سلسلة إدخال معينة) هي q أو q'، فيمكننا إضافة انتقال ε بين هاتين الحالتين، وبالتالي وضع الأوتوماتون في كلتا الحالتين في آنٍ واحد.

التعريف الرسمي

يتم تمثيل NFA-ε رسميًا بواسطة مجموعة من 5 عناصر ،(سؤال،Σ،دلتا،q0،F){\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}، ويتألف من

هنا،P(سؤال){\displaystyle {\mathcal {P}}(Q)}يشير إلى مجموعة القوى لـسؤال{\displaystyle Q}وε{\displaystyle \varepsilon }يشير إلى سلسلة نصية فارغة.

إغلاق إبسيلون لحالة أو مجموعة من الحالات

بالنسبة للدولةq∈سؤال{\displaystyle q\in Q}، يتركهـ(q){\displaystyle E(q)}تشير إلى مجموعة الحالات التي يمكن الوصول إليها منq{\displaystyle q}من خلال تتبع انتقالات إبسيلون في دالة الانتقالدلتا{\displaystyle \delta }، أي، ص∈هـ(q){\displaystyle p\in E(q)}إذا كان هناك تسلسل من الحالاتq1،...،qك{\displaystyle q_{1},...,q_{k}}بحيث

  • q1=q{\displaystyle q_{1}=q}،
  • qأنا+1∈دلتا(qأنا،ε){\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}لكل1≤أنا<ك{\displaystyle 1\leq i<k}، و
  • qك=ص{\displaystyle q_{k}=p}.

هـ(q){\displaystyle E(q)}يُعرف باسم إغلاق إبسيلون (أو إغلاق إبسيلون )q{\displaystyle q}.

الإغلاق-ε لمجموعةP{\displaystyle P}تُعرَّف حالات آلة الحالة المحدودة غير القطعية بأنها مجموعة الحالات التي يمكن الوصول إليها من أي حالة فيP{\displaystyle P}بعد انتقالات إبسيلون. رسميًا، لـP⊆سؤال{\displaystyle P\subseteq Q}، يُعرِّفهـ(P)=⋃q∈Pهـ(q){\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}.

دالة انتقال موسعة

على غرار NFA بدون حركات إبسيلون، دالة الانتقالدلتا{\displaystyle \delta }يمكن توسيع نطاق NFA-ε ليشمل السلاسل النصية. بشكل غير رسمي،دلتا*(q،w){\displaystyle \delta ^{*}(q,w)}تشير إلى مجموعة جميع الحالات التي ربما يكون الجهاز الآلي قد وصل إليها عند بدء التشغيل في الحالةq∈سؤال{\displaystyle q\in Q}وقراءة السلسلةw∈Σ*.{\displaystyle w\in \Sigma ^{*}.} الوظيفةدلتا*:سؤال×Σ*→P(سؤال){\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}يمكن تعريفها بشكل متكرر على النحو التالي.

  • دلتا*(q،ε)=هـ(q){\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}لكل ولايةq∈سؤال،{\displaystyle q\in Q,}وأينهـ{\displaystyle E}يشير إلى إغلاق إبسيلون؛
بصورة غير رسمية: قد تؤدي قراءة السلسلة الفارغة إلى تغيير حالة الآلة.q{\displaystyle q}إلى أي حالة من حالات إغلاق إبسيلون لـq.{\displaystyle q.}
  • دلتا*(q،wأ)=⋃ر∈دلتا*(q،w)هـ(دلتا(ر،أ))،{\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}لكل ولايةq∈سؤال،{\displaystyle q\in Q,}كل وترw∈Σ*{\displaystyle w\in \Sigma ^{*}}وكل رمزأ∈Σ.{\displaystyle a\in \Sigma .}
بشكل غير رسمي: قراءة السلسلةw{\displaystyle w}قد يقود الآلة من الحالةq{\displaystyle q}إلى أي ولايةر{\displaystyle r}في المجموعة المحسوبة بشكل متكرردلتا*(q،w){\displaystyle \delta ^{*}(q,w)}بعد ذلك، قراءة الرمزأ{\displaystyle a}قد يقودها منر{\displaystyle r}إلى أي ولاية في إغلاق إبسيلون لـدلتا(ر،أ).{\displaystyle \delta (r,a).}

يقال إن الآلة تقبل سلسلة نصيةw{\displaystyle w}لو

دلتا*(q0،w)∩F≠∅،{\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}

أي إذا كان القراءةw{\displaystyle w}قد يؤدي ذلك إلى تحريك الآلة من حالة بدء التشغيلq0{\displaystyle q_{0}}إلى دولة مقبولة فيF.{\displaystyle F.}[ 11 ]

مثال

مخطط الحالة لـ M

يتركم{\displaystyle M}ليكن NFA-ε، بأبجدية ثنائية، يحدد ما إذا كان المدخل يحتوي على عدد زوجي من الأصفار أو عدد زوجي من الآحاد. لاحظ أن صفرًا من الأصفار هو عدد زوجي من الآحاد أيضًا.

في الترميز الرسمي، ليكنم=({S0،S1،S2،S3،S4}،{0،1}،دلتا،S0،{S1،S3}){\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}حيث علاقة الانتقالدلتا{\displaystyle \delta }يمكن تعريفها بواسطة جدول انتقال الحالة هذا :

مدخل
ولاية
01ε
S 0{}{}{ S 1 , S 3 }
S 1{ S 2 }{ S 1 }{}
S 2{ S 1 }{ S 2 }{}
S 3{ S 3 }{ S 4 }{}
S 4{ S 4 }{ S 3 }{}

م{\displaystyle M}يمكن اعتبارها اتحادًا بين نظامين من أنظمة إدارة البيانات : أحدهما مع الدول{S1،S2}{\displaystyle \{S_{1},S_{2}\}}والآخر مع الولايات{S3،S4}{\displaystyle \{S_{3},S_{4}\}}لغةم{\displaystyle M}يمكن وصفها باللغة المنتظمة التي يوفرها هذا التعبير النمطي(1*01*01*)*∪(0*10*10*)*{\displaystyle (1^{*}01^{*}01^{*})^{*}\cup (0^{*}10^{*}10^{*})^{*}}نُعرّفم{\displaystyle M}باستخدام حركات إبسيلون ولكنم{\displaystyle M}يمكن تعريفها دون استخدام حركات إبسيلون.

مكافئ لقانون العقود الآجلة الوطني

لإثبات أن NFA-ε مكافئ لـ NFA، لاحظ أولاً أن NFA هي حالة خاصة من NFA-ε، لذلك يبقى أن نثبت أنه لكل NFA-ε، يوجد NFA مكافئ.

بافتراض وجود NFA مع تحركات إبسيلونم=(سؤال،Σ،دلتا،q0،F)،{\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),} تعريف NFAم′=(سؤال،Σ،دلتا′،q0،F′)،{\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}أين

F′={F∪{q0} لو هـ(q0)∩F≠{}F خلاف ذلك {\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}

و

دلتا′(q،أ)=دلتا*(q،أ){\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}لكل ولايةq∈سؤال{\displaystyle q\in Q}وكل رمزأ∈Σ،{\displaystyle a\in \Sigma ,}باستخدام دالة الانتقال الموسعةدلتا*{\displaystyle \delta ^{*}}كما هو موضح أعلاه.

يجب التمييز بين دوال الانتقال لـم{\displaystyle M}وم′،{\displaystyle M',}بمعنى.دلتا{\displaystyle \delta }ودلتا′،{\displaystyle \delta ',}وامتداداتها إلى السلاسل،دلتا*{\displaystyle \delta ^{*}}ودلتا′*،{\displaystyle \delta '^{*},}على التوالي. بحسب التصميم،م′{\displaystyle M'}لا يحتوي على انتقالات إبسيلون.

يمكن إثبات ذلكدلتا′*(q0،w)=دلتا*(q0،w){\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}لكل سلسلةw≠ε{\displaystyle w\neq \varepsilon }، عن طريق الاستقراء على طولw.{\displaystyle w.}

وبناءً على ذلك، يمكن للمرء أن يوضح أندلتا′*(q0،w)∩F′≠{}{\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}إذا، وفقط إذا،دلتا*(q0،w)∩F≠{}،{\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}لكل سلسلةw∈Σ*:{\displaystyle w\in \Sigma ^{*}:}

  • لوw=ε،{\displaystyle w=\varepsilon ,}ويترتب على ذلك تعريفF′.{\displaystyle F'.}
  • وإلا، فليكنw=vأ{\displaystyle w=va}معv∈Σ*{\displaystyle v\in \Sigma ^{*}}وأ∈Σ.{\displaystyle a\in \Sigma .}
مندلتا′*(q0،w)=دلتا*(q0،w){\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}وF⊆F′،{\displaystyle F\subseteq F',}لدينادلتا′*(q0،w)∩F′≠{}⇐دلتا*(q0،w)∩F≠{}؛{\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}لا يزال يتعين علينا إظهار "⇒{\displaystyle \Rightarrow }" اتجاه.
  • لودلتا′*(q0،w){\displaystyle \delta '^{*}(q_{0},w)}يحتوي على ولاية فيF′∖{q0}،{\displaystyle F'\setminus \{q_{0}\},}ثمدلتا*(q0،w){\displaystyle \delta ^{*}(q_{0},w)}تحتوي على نفس الولاية، التي تقع فيF{\displaystyle F}.
  • لودلتا′*(q0،w){\displaystyle \delta '^{*}(q_{0},w)}يتضمنq0،{\displaystyle q_{0},}وq0∈F،{\displaystyle q_{0}\in F,}ثم دلتا*(q0،w){\displaystyle \delta ^{*}(q_{0},w)}كما يحتوي على ولاية فيF،{\displaystyle F,}بمعنى.q0.{\displaystyle q_{0}.}
  • لودلتا′*(q0،w){\displaystyle \delta '^{*}(q_{0},w)}يتضمنq0،{\displaystyle q_{0},}وq0∉F،{\displaystyle q_{0}\not \in F,}لكنq0∈F′،{\displaystyle q_{0}\in F',}ثم توجد حالة فيهـ(q0)∩F{\displaystyle E(q_{0})\cap F}ويجب أن تكون الحالة نفسها فيدلتا*(q0،w)=⋃ر∈دلتا*(q،v)هـ(دلتا(ر،أ)).{\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}[ 12 ]

بما أن NFA مكافئ لـ DFA، فإن NFA-ε مكافئ أيضًا لـ DFA.

خصائص الإغلاق

آلة الحالة المحدودة غير القطعية المركبة (NFA) تقبل اتحاد لغات آلات الحالة المحدودة غير القطعية المعطاة N ( s ) و N ( t ) . بالنسبة لسلسلة الإدخال w في اتحاد اللغات، تتبع الآلة المركبة انتقالًا من نوع ε من q إلى حالة البداية (الدائرة الملونة على اليسار) لآلة فرعية مناسبة - N ( s ) أو N ( t ) - والتي، باتباع w ، قد تصل إلى حالة قبول (الدائرة الملونة على اليمين)؛ ومن هناك، يمكن الوصول إلى الحالة f بانتقال آخر من نوع ε. نظرًا لانتقالات ε، فإن آلة الحالة المحدودة غير القطعية المركبة غير قطعية بشكل صحيح حتى لو كانت كل من N ( s ) و N ( t ) آلات حالة محدودة قطعية (DFA)؛ وعلى العكس من ذلك، فإن بناء آلة حالة محدودة قطعية للغة الاتحاد (حتى لو كانت اثنتين من آلات الحالة المحدودة القطعية) أكثر تعقيدًا بكثير.

تُعتبر مجموعة اللغات التي تتعرف عليها آلات الحالة المحدودة غير القطعية (NFAs) مغلقةً تحت العمليات التالية. تُستخدم عمليات الإغلاق هذه في خوارزمية تومسون للبناء ، التي تُنشئ آلة حالة محدودة غير قطعية من أي تعبير نمطي . كما يمكن استخدامها لإثبات أن آلات الحالة المحدودة غير القطعية تتعرف تحديدًا على اللغات النمطية .

  • الاتحاد (انظر الصورة)؛ أي إذا تم قبول اللغة L 1 بواسطة NFA A 1 و L 2 بواسطة A 2 ، فإنه يمكن إنشاء NFA A u يقبل اللغة L 1 ∪ L 2 .
  • التقاطع؛ وبالمثل، من A 1 و A 2 يمكن إنشاء NFA A i الذي يقبل L 1 ∩ L 2 .
  • سلسلة
  • النفي؛ وبالمثل، من A 1 يمكن إنشاء NFA A n التي تقبل Σ * \ L 1 .
  • إغلاق كلين

بما أن NFAs تعادل الآلات المحدودة غير الحتمية ذات الحركات ε (NFA-ε)، فإنه يمكن إثبات الإغلاقات المذكورة أعلاه باستخدام خصائص الإغلاق لـ NFA-ε.

ملكيات

تبدأ الآلة من الحالة الابتدائية المحددة وتقرأ سلسلة من الرموز من أبجديتها . تستخدم الآلة دالة انتقال الحالة Δ لتحديد الحالة التالية بالاعتماد على الحالة الحالية، والرمز المقروء للتو، أو السلسلة الفارغة. مع ذلك، "لا تعتمد الحالة التالية للآلة غير القطعية على حدث الإدخال الحالي فحسب، بل تعتمد أيضًا على عدد غير محدد من أحداث الإدخال اللاحقة. وحتى وقوع هذه الأحداث اللاحقة، لا يمكن تحديد حالة الآلة". [ 13 ] إذا كانت الآلة في حالة قبول عند انتهاء القراءة، يُقال إنها تقبل السلسلة، وإلا يُقال إنها ترفضها.

مجموعة جميع السلاسل النصية التي يقبلها جهاز NFA هي اللغة التي يقبلها هذا الجهاز. وهذه اللغة هي لغة منتظمة .

لكل آلة حالة محدودة غير حتمية (NFA)، يمكن إيجاد آلة حالة محدودة حتمية (DFA) تقبل اللغة نفسها. لذا، من الممكن تحويل آلة NFA موجودة إلى آلة DFA بهدف تنفيذ آلة أبسط (ربما). يمكن تحقيق ذلك باستخدام بناء مجموعة القوى ، والذي قد يؤدي إلى زيادة أسية في عدد الحالات اللازمة. للاطلاع على برهان رسمي لبناء مجموعة القوى، يُرجى مراجعة مقال بناء مجموعة القوى .

تطبيق

هناك العديد من الطرق لتطبيق نظام NFA:

  • قم بتحويلها إلى ما يعادلها من DFA. في بعض الحالات، قد يؤدي ذلك إلى زيادة هائلة في عدد الحالات. [ 14 ]
  • احتفظ ببنية بيانات تضم جميع الحالات التي قد يكون عليها الجهاز غير الحتمي (NFA) حاليًا. عند استهلاك رمز إدخال، اجمع نتائج دالة الانتقال المطبقة على جميع الحالات الحالية للحصول على مجموعة الحالات التالية؛ إذا كانت عمليات الانتقال من النوع ε مسموحة، فقم بتضمين جميع الحالات التي يمكن الوصول إليها من خلال هذه العملية (إغلاق من النوع ε). تتطلب كل خطوة على الأكثر s² عملية حسابية، حيث s هو عدد حالات الجهاز غير الحتمي. عند استهلاك رمز الإدخال الأخير، إذا كانت إحدى الحالات الحالية حالة نهائية، يقبل الجهاز السلسلة. يمكن معالجة سلسلة بطول n في زمن O ( ns² )، [ 15 ] ومساحة O ( s ) .
  • أنشئ نسخًا متعددة. لكل قرار ذي n اتجاه، تُنشئ آلة الحالة المحدودة غير القطعية (NFA) ما يصل إلى n - 1 نسخة من الآلة. ستدخل كل نسخة حالة منفصلة. إذا كانت نسخة واحدة على الأقل من آلة الحالة المحدودة غير القطعية في حالة القبول عند استهلاك رمز الإدخال الأخير، فستقبل الآلة. (يتطلب هذا أيضًا تخزينًا خطيًا بالنسبة لعدد حالات آلة الحالة المحدودة غير القطعية، حيث يمكن أن تكون هناك آلة واحدة لكل حالة من حالات آلة الحالة المحدودة غير القطعية).
  • انشر الرموز بشكل صريح عبر بنية الانتقال في الأوتوماتا غير القطعية، وقم بالمطابقة كلما وصل رمز إلى الحالة النهائية. يكون هذا مفيدًا أحيانًا عندما تحتاج الأوتوماتا غير القطعية إلى ترميز سياق إضافي حول الأحداث التي أدت إلى بدء الانتقال. (للاطلاع على تطبيق يستخدم هذه التقنية لتتبع مراجع الكائنات، راجع Tracematches.) [ 16 ]

تعقيد

  • يمكن حل مشكلة الفراغ في حالة الأوتوماتا غير القطعية (NFA) في زمن خطي، أي التحقق مما إذا كانت لغة الأوتوماتا غير القطعية المعطاة فارغة. وللقيام بذلك، يمكننا ببساطة إجراء بحث معمق أولاً من الحالة الابتدائية والتحقق مما إذا كان من الممكن الوصول إلى حالة نهائية معينة.
  • يُعد اختبار ما إذا كانت آلة الحالة المحدودة غير القطعية (NFA) شاملة ، أي ما إذا كانت هناك سلسلة لا تقبلها، مسألةً كاملةً من فئة PSPACE . [ 17 ] ونتيجةً لذلك، ينطبق الأمر نفسه على مسألة الاحتواء ، أي، بالنظر إلى آلتين من آلات الحالة المحدودة غير القطعية، هل لغة إحداهما مجموعة جزئية من لغة الأخرى؟
  • إذا أُدخلت آلة حالة نهائية غير قطعية A وعدد صحيح n، فإن مسألة عدّ الكلمات التي يبلغ طولها n والتي تقبلها A تُعدّ مسألةً معقدةً للغاية؛ فهي من فئة #P -hard . في الواقع، تُعتبر هذه المسألة كاملةً (في ظلّ الاختزالات المُقتصدة ) بالنسبة لفئة التعقيد SpanL . [ 18 ]

تطبيق قانون العقود الوطنية

تتشابه الآلات غير القطعية المحدودة (NFAs) والآلات القطعية المحدودة (DFAs) في أن اللغة التي تتعرف عليها الآلة غير القطعية المحدودة تتعرف عليها الآلة القطعية المحدودة أيضًا، والعكس صحيح. يُعدّ إثبات هذا التكافؤ مهمًا ومفيدًا، فهو مفيد لأن بناء آلة غير قطعية محدودة للتعرف على لغة معينة يكون أحيانًا أسهل بكثير من بناء آلة قطعية محدودة لتلك اللغة. كما أنه مهم لأن الآلات غير القطعية المحدودة تُستخدم لتقليل تعقيد العمليات الحسابية اللازمة لإثبات العديد من الخصائص المهمة في نظرية الحوسبة . على سبيل المثال، من الأسهل بكثير إثبات خصائص الإغلاق للغات المنتظمة باستخدام الآلات غير القطعية المحدودة مقارنةً بالآلات القطعية المحدودة.

انظر أيضاً

ملحوظات

  1. ↑ مارتن، جون (2010). مقدمة في اللغات ونظرية الحوسبة . ماكجرو هيل. ص  108. ISBN 978-0071289429.
  2. ↑ رابين وسكوت 1959 .
  3. ↑ قد يؤدي تسلسل الاختيار إلى "طريق مسدود" حيث لا يوجد انتقال قابل للتطبيق على رمز الإدخال الحالي؛ في هذه الحالة يعتبر غير ناجح.
  4. 1 2 هوبكروفت وأولمان 1979 ، ص 19-20.
  5. 1 2 ألفريد ف. أهو وجون إي. هوبكروفت وجيفري د. أولمان (1974). تصميم وتحليل خوارزميات الحاسوب . ريدينغ/ماساتشوستس: أديسون-ويسلي. ISBN 0-201-00029-6.
  6. 1 2 هوبكروفت، موتاني وأولمان 2006 ، ص 55-6.
  7. ↑ Sipser 1997 ، ص 48.
  8. ↑ Sipser 1997 ، ص 54.
  9. ↑ هوبكروفت وأولمان 1979 ، ص 21.
  10. ↑ هوبكروفت، موتاني وأولمان 2006 ، ص 59.
  11. ↑ هوبكروفت وأولمان 1979 ، ص 25.
  12. ↑ هوبكروفت وأولمان 1979 ، ص 26-27.
  13. ↑ قاموس FOLDOC المجاني على الإنترنت للحوسبة، آلة الحالة المحدودة
  14. ^ كريس كالابرو (27 فبراير 2005). "تضخم NFA إلى DFA" (PDF) . cseweb.ucsd.edu . تم الاسترجاع في 6 مارس 2023 .
  15. ↑ هوبكروفت، موتاني وأولمان 2006 ، ص 154-155.
  16. ↑ ألان، سي.، أفغوستينوف، ب.، كريستنسن، أ.س.، هندري، ل.، كوزينز، س.، لهوتاك، أ.، دي مور، أ.، سيريني، د.، سيتامبالام، ج.، وتيبيل، ج. 2005. إضافة مطابقة التتبع مع المتغيرات الحرة إلى AspectJ. مؤرشف في 18 سبتمبر 2009 على Wayback Machine . في وقائع المؤتمر السنوي العشرين لجمعية ACM SIGPLAN حول البرمجة الكائنية والأنظمة واللغات والتطبيقات (سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية، 16-20 أكتوبر 2005). OOPSLA '05. ACM، نيويورك، نيويورك، 345-364.
  17. ↑ تاريخيًا، ورد في: ماير، أ. ر.؛ ستوكمير، ل. ج. (25-10-1972). "مشكلة التكافؤ للتعبيرات النمطية مع التربيع تتطلب مساحة أسية". الندوة السنوية الثالثة عشرة حول نظرية التبديل والأتمتة (Swat 1972) . الولايات المتحدة الأمريكية: جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 125-129 . doi : 10.1109/SWAT.1972.29 . للاطلاع على عرض تقديمي حديث، انظر
  18. ↑ ألفاريز، كارمي؛ جينر، بيرجيت (4 يناير 1993). "فئة عدّ صعبة للغاية في فضاء لوغاريتمي" . علوم الحاسوب النظرية . 107 (1): 3-30 . doi : 10.1016/0304-3975(93)90252-O . ISSN 0304-3975 . 

مراجع