أتمتة الخيوط

في نظرية الأوتوماتا ، يعتبر الأوتوماتا الخيطي (الجمع: الأوتوماتا) نوعًا موسعًا من الأوتوماتا ذات الحالة المحدودة التي تتعرف على فئة لغوية حساسة للسياق بشكل طفيف فوق اللغات المجاورة للشجرة . ^{[ 1 ]}

يتكون أوتوماتون الخيوط من

• مجموعة N من الحالات، ^{[ ملاحظة 1 ]}
• مجموعة Σ من الرموز الطرفية،
• حالة البداية A _S ∈ N ،
• الحالة النهائية A _F ∈ N ،
• مجموعة U من مكونات المسار،
• دالة جزئية δ: N → U ^⊥ ، حيث U ^⊥ = U ∪ {⊥} لـ ⊥ ∉ U ،
• مجموعة محدودة Θ من التحولات.

المسار u₁ _... uₙ _∈ U ^* هو سلسلة من مكونات المسار uᵢ ∈ U _؛ قد _تكون قيمة n تساوي صفرًا، ويُرمز للمسار الفارغ بالرمز ε. يأخذ الخيط الشكل u₁ ... uₙ : A ، حيث u₁ ... uₙ ∈ U * هو _مسار ، و A ∈ N هي حالة _. ^مخزن الخيوط S هو مجموعة منتهية من الخيوط _، يُنظر إليه كدالة جزئية من U ^* إلى N ، بحيث تكون dom ( S ) مغلقة بالبادئة .

تُعرَّف تهيئة أوتوماتون الخيوط بأنها ثلاثية ⟨l , p , S⟩ ، حيث يُمثل l الموضع الحالي في سلسلة الإدخال، و p الخيط النشط، و S مخزن الخيوط الذي يحتوي على p . التهيئة الأولية هي ⟨0 , ε, {ε: A S _} ⟩ . أما التهيئة النهائية فهي ⟨n , u , {ε: A _S , u : A _F } ⟩ ، حيث n هو طول سلسلة الإدخال، و _{u اختصار لـ δ(AS} ) . قد يتخذ الانتقال في المجموعة Θ أحد الأشكال التالية، ويُغير تهيئة الأوتوماتون الحالية بالطريقة التالية:

• SWAP B → _a C :  يستهلك رمز الإدخال a ، ويغير حالة الخيط النشط:

يُغيّر التكوين من ⟨ l , p , S ∪{ p : B } ⟩ إلى ⟨ l +1, p , S ∪{ p : C } ⟩   

• تبديل B → _ε C :  مشابه، لكنه لا يستهلك أي مدخلات:

التغييرات ⟨ l , p , S ∪{ p : B } ⟩ إلى ⟨ l , p , S ∪{ p : C } ⟩   

• PUSH C :  ينشئ سلسلة فرعية جديدة، ويعلق سلسلة العمليات الرئيسية الخاصة به:

التغييرات ⟨ l , p , S ∪{ p : B } ⟩ إلى ⟨ l , pu , S ∪{ p : B , pu : C } ⟩ حيث u =δ( B ) و pu ∉dom( S )    

• POP [ B ] C :  ينهي الخيط النشط، ويعيد التحكم إلى الخيط الأصل:

التغييرات ⟨ l , pu , S ∪{ p : B , pu : C } ⟩ إلى ⟨ l , p , S ∪{ p : C } ⟩ حيث δ( C )=⊥ و pu ∉dom( S )    

• SPUSH [ C ] D :  يستأنف سلسلة فرعية معلقة من السلسلة النشطة:

التغييرات ⟨ l , p , S ∪{ p : B , pu : C } ⟩ إلى ⟨ l , pu , S ∪{ p : B , pu : D } ⟩ حيث u =δ( B )    

• SPOP [ B ] D :  يستأنف العملية الأصلية للخيط النشط:

التغييرات ⟨ l , pu , S ∪{ p : B , pu : C } ⟩ إلى ⟨ l , p , S ∪{ p : D , pu : C } ⟩ حيث δ( C )=⊥    

يمكن إثبات أن δ( B ) = u لانتقالات POP و SPOP ، وأن δ( C ) = ⊥ لانتقالات SPUSH . ^{[ 2 ]}

يتم قبول سلسلة الإدخال بواسطة الآلة إذا كان هناك تسلسل من التحولات التي تغير التكوين الأولي إلى التكوين النهائي.