Ip avtomati - Thread automaton

Yilda avtomatlar nazariyasi, avtomat avtomat (ko'plik: automata) kengaytirilgan turi cheklangan davlat avtomatlari a taniydi kontekstga sezgir bo'lgan til sinfi yuqorida daraxtga tutash tillar.[1]

Rasmiy ta'rif

A avtomat avtomat dan iborat

  • to'plam N davlatlar,[eslatma 1]
  • terminal belgilarining Σ to'plami,
  • boshlang'ich holati AS ∈ N,
  • yakuniy holat AF ∈ N,
  • to'plam U yo'l komponentlari,
  • qisman funktsiya δ: N → U⊥, qayerda U⊥ = U ⊥ ∉ uchun ⊥ {⊥} U,
  • o'tishning cheklangan to'plami.

A yo'l siz1...sizn ∈ U* - bu yo'l komponentlari qatori sizmen ∈ U; n 0 bo'lishi mumkin, bo'sh yo'l ε.A bilan belgilanadi ip shaklga ega siz1...sizn:A, qayerda siz1...sizn ∈ U* bu yo'l va A ∈ N davlatdir iplar do'koni S dan qisman funktsiya sifatida qaraladigan sonli iplar to'plami U* ga N, shu kabi dom(S) yopiq tomonidan prefiks.

Ipli avtomat konfiguratsiya uch karra ‹l,p,S›, Qaerda l kirish satridagi joriy holatni bildiradi, p faol ip va S o'z ichiga olgan iplar do'koni p.The dastlabki konfiguratsiya bu ‹0, ε, {ε:AS} ›. The yakuniy konfiguratsiya bu ‹n,siz, {ε:AS,siz:AF} ›, Qaerda n bu kirish satrining uzunligi va siz qisqartiradi δ (AS) .A o'tish Θ to'plamida quyidagi shakllardan biri bo'lishi mumkin va joriy avtomat konfiguratsiyasini quyidagi tarzda o'zgartiradi:

  • Almashtirish B →a C: kirish belgisini sarflaydi ava faol ipning holatini o'zgartiradi:
konfiguratsiyani ‹dan o'zgartiradil,p,S∪{p:B} ›Dan‹l+1,p,S∪{p:C}›
  • Almashtirish B →ε C: o'xshash, lekin hech qanday ma'lumot sarf qilmaydi:
o'zgarishlarl,p,S∪{p:B} ›Dan‹l,p,S∪{p:C}›
  • DURANG C: yangi subtread yaratadi va uning asosiy yo'nalishini to'xtatadi:
o'zgarishlarl,p,S∪{p:B} ›Dan‹l,pu,S∪{p:B,pu:C} ›Qayerda siz= δ (B) va puDom (S)
  • POP [B]C: faol ipni tugatadi, boshqaruvni ota-onasiga qaytaradi:
o'zgarishlarl,pu,S∪{p:B,pu:C} ›Dan‹l,p,S∪{p:C} ›Qaerda δ (C) = ⊥ va puDom (S)
  • SPUSH [C] D.: faol ipning to'xtatilgan pastki chizig'ini davom ettiradi:
o'zgarishlarl,p,S∪{p:B,pu:C} ›Dan‹l,pu,S∪{p:B,pu:D.} ›Qayerda siz= δ (B)
  • SPOP [B] D.: faol ipning ota-onasini davom ettiradi:
o'zgarishlarl,pu,S∪{p:B,pu:C} ›Dan‹l,p,S∪{p:D.,pu:C} ›Qaerda δ (C)=⊥

Shuni isbotlash mumkin δ (B)=siz uchun POP va SPOP o'tish va δ (C) = ⊥ uchun SPUSH o'tish.[2]

Kirish satri qabul qilindi boshlang'ichni yakuniy konfiguratsiyaga o'zgartiradigan o'tish ketma-ketligi mavjud bo'lsa, avtomat tomonidan.

Izohlar

  1. ^ deb nomlangan terminal bo'lmagan belgilar Villemonte tomonidan (2002), p.1r

Adabiyotlar

  1. ^ Villemonte de la Klerjeri, Erik (2002). "Kontekstga sezgir bo'lgan tillarni avtomatika bilan tahlil qilish". COLING '02 Kompyuter lingvistikasi bo'yicha 19-xalqaro konferentsiya materiallari. 1 (3): 1–7. doi:10.3115/1072228.1072256. Olingan 2016-10-15.
  2. ^ Villemonte (2002), p.1r-2r