Кіріспе
Ағаш автоматының өзгеше ұғымы. Ағаш автоматы – мемлекеттік машинаның бір түрі. Ағаш автоматтары дәстүрлі мемлекеттік машиналардың тізбектерімен емес, ағаш құрылымдарымен жұмыс істейді. Келесі мақалада ағаштардың реттелген тілдеріне сәйкес келетін тармақталған ағаш автоматтары қарастырылады. Классикалық автоматтар сияқты, шекті ағаш автоматтары (FTA) детерминистік немесе детерминистік емес болуы мүмкін. Автомат кіріс ағашын қалай өңдейтініне қарай, шекті ағаш автоматтары екі түрге бөлінеді: (а) төменнен жоғары, (б) жоғарыдан төмен. Бұл маңызды мәселе, себебі детерминистік емес (ND) жоғарыдан төмен және ND төменнен жоғары ағаш автоматтарының көрініс беру қабілеті тең болғанымен, детерминистік жоғарыдан төмен автоматтар детерминистік төменнен жоғары автоматтардан әлдеқайда әлсіз, өйткені детерминистік жоғарыдан төмен ағаш автоматтарымен сипатталатын ағаш қасиеттері тек жол қасиеттеріне ғана байланысты болуы мүмкін. (Детерминистік төменнен жоғары автоматтар ND ағаш автоматтарымен бірдей қуатты.)
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although non deterministic (ND) top down and ND bottom up tree automata are equivalent in expressive power, deterministic top down automata are strictly less powerful than their deterministic bottom up counterparts, because tree properties specified by deterministic top down tree automata can only depend on path properties. (Deterministic bottom up tree automata are as powerful as ND tree automata.)
Таңдау мүмкіндігі
Төменнен жоғары автоматта, егер t-ден басталып, q(t) арқылы аяқталатын азайту болса, t (яғни ағаш) негізгі термині қабылданады, мұнда q – соңғы күй. Жоғарыдан төменге автомат үшін, егер q(t)-ден басталып, t арқылы аяқталатын азайту болса, t негізгі термині қабылданады, мұнда q – бастапқы күй. Ағаш тілі L(A) – ағаш автоматтың A қабылдайтын немесе танитын барлық негізгі терминдердің жиынтығы. Егер оны қабылдайтын ағаш автомат болса, негізгі терминдер жиынтығы танылады. Сызықтық (яғни, арлықты сақтайтын) ағаш гомоморфизмі танымалдылықты сақтайды.
Толықтылық және қысқарту
Детерминистік емес шекті ағаш автоматтары толық деп есептеледі, егер кез келген мүмкін символдар мен күйлер комбинациясы үшін кем дегенде бір ауысу ережесі болса. Күй q қолжетімді болып есептеледі, егер t негіздік термисі бар болса, сол термистен q(t) күйіне дейін азайту мүмкін болса. NFTA азайтылған деп есептеледі, егер оның барлық күйлері қолжетімді болса.
Құбырлау леммасы
L танылатын ағаш тіліндегі әрбір жеткілікті үлкен t негіздік терминін тігінен үш бөлікке бөлуге болады, ортаңғы бөлігінің кез келген қайталануы ("пампинг") нәтижесінде алынған термин L тілінде қалатындай етіп. Жоғарыдағы мысалда келтірілген бульдік мәндердің барлық шекті тізімдерінің тілі үшін, k=2 биіктік шегінен асып кеткен барлық терминдерді "сорғылауға" болады, себебі олар міндетті түрде мынадай элементтерді қамтуы керек: (, (,) ) , (,(, (,) )) , (,(,(, (,) ))) , барлығы да сол тілге жатады.
For the language of all finite lists of boolean values from the above example, all terms beyond the height limit k=2 can be pumped, since they need to contain an occurrence of For example,
(, (,) ) , (,(, (,) )) , (,(,(, (,) ))) ,
all belong to that language.
Жабылу
Тануға болатын ағаш тілдерінің класы біріктіру, толықтыру және қиылысу операциялары бойынша жабық.