Back

ⓘ Аутомат бесконачног стабла




                                     

ⓘ Аутомат бесконачног стабла

У информатици и математичкој логици, аутомат бесконачног стабла је коначна машина која се бави структуром бесконачног стабла. Може се посматрати као продужетак коначног аутомата стабла, која прихвата само коначне структуре стабла. Такође се може посматрати као проширење неких бесконачних аутомата речи, као што су Büchi и Muller аутомат.

Коначни аутомат који ради на бесконачном стаблу је први пут користио Рабин за доказивање одлучивости монадне логике другог реда. Касније је примећено да су аутомат стабла и логичке теорије уско повезани и омогућавају да проблем одлучивања у логици буде смањен на проблем одлучивања аутомата.

                                     

1. Дефиниција

Аутомат бесконачног стабла ради преко Σ {\displaystyle \Sigma } -обележеног стабла. Постоји много благо различитих формулација аутомата стабла. Овде је једна од формулација описана. Аутомат бесконачног стабла је коначан низ A = {\displaystyle A=\Sigma,D,Q,\delta,q_{0},F} у коме,

  • Σ {\displaystyle \Sigma } је писмо.
  • F ⊆ Σ ω {\displaystyle F\subseteq \Sigma ^{\omega }} је прихватање услова.
  • Q {\displaystyle Q} је коначан скуп стања.
  • D ⊂ N {\displaystyle D\subset \mathbb {N} } је коначан скуп. Сваки елемент D {\displaystyle D} је дозвољен степен у улазном стаблу.
  • q 0 ∈ Q {\displaystyle q_{0}\in Q} је почетно стање аутомата.
  • δ: Q × Σ × D → 2 Q ∗ {\displaystyle \delta:Q\times \Sigma \times D\rightarrow 2^{Q^{*}}} је транзитна веза која пресликава стање аутомата q ∈ Q {\displaystyle q\in Q}, улазно слово σ ∈ Σ {\displaystyle \sigma \in \Sigma }, и степен d ∈ D {\displaystyle d\in D} у скуп d-торке стања.
                                     

2. Покретање

Покретање аутомата стабла A {\displaystyle A} преко Σ {\displaystyle \Sigma } -означеног стабла T, V {\displaystyle T,V} је Q {\displaystyle Q} -означено стабло T r, r {\displaystyle T_{r},r}. Претпоставимо да је аутомат стабла у стању q {\displaystyle q} и да је достигао до чвора t означеног са σ ∈ Σ {\displaystyle \sigma \in \Sigma } улазног стабла. d t {\displaystyle dt} је степен чвора t. Затим, аутомат наставља селектујући коначан низ q 1., q d t) {\displaystyle q_{1}.,q_{dt})} из скупа δ q, σ, d t) {\displaystyle \delta q,\sigma,dt)} и цепању у d t {\displaystyle dt} копије себе. За сваки 0 < i ≤ d t {\displaystyle 0

                                     
  • што је скуп инструкција рачунара, неки програмски језик, или ћелијски аутомат је рекао да је Тјуринг потпун или рачунски универзалан ако се може користити
  • не може да натера машину да уђе у бесконачну петљу. Као тривијалан пример, машина која имплементира коначно стабло одлучивања ће се увек зауставити. Не
  • Тјуринг у својим радовима дефинисањем Тјурингове машине. То је примитиван аутомат мисаона творевина, али поседује могућност извођења неколико операција

Users also searched:

...