Automat drzewny - Tree automaton

Drzewo automat to rodzaj machiny państwowej . Automaty drzewne zajmują się strukturami drzewiastymi , a nie ciągami bardziej konwencjonalnych maszyn stanowych.

Poniższy artykuł dotyczy automatów do rozgałęziania drzew, które odpowiadają regularnym językom drzew .

Podobnie jak w przypadku automatów klasycznych, automaty z drzewami skończonymi (FTA) mogą być automatami deterministycznymi lub nie. W zależności od tego, jak automat przetwarza drzewo wejściowe, automaty z drzewami skończonymi mogą być dwojakiego rodzaju: (a) od dołu do góry, (b) od góry do dołu. Jest to istotna kwestia, ponieważ chociaż niedeterministyczne (ND) automaty zstępujące i ND z dołu do góry są równoważne pod względem mocy wyrazu, to deterministyczne automaty zstępujące są ściśle słabsze niż ich deterministyczne odpowiedniki z dołu do góry, ponieważ własności drzew określone przez deterministyczne automaty drzewa odgórnego mogą zależeć tylko od właściwości ścieżki. (Deterministyczne automaty drzewa od dołu do góry są równie potężne jak automaty drzewa ND.)

Definicje

Oddolne skończonych drzewa automatu przez F, definiuje się jako krotka ( Q , F , Q, F , A), gdzie Q jest zestawem stanów, F to miejsce alfabetu (tj alfabetu których symbole mają powiązaną Arity ) , Q fQ jest zbiorem stanów końcowych, a Δ jest zbiorem reguł przejściowych postaci f ( q 1 ( x 1 ),..., q n ( x n )) → q ( f ( x 1 , ..., x n )), dla n -ary fK , Q , Q iP , a x i zmienne oznaczający poddrzewa. Oznacza to, że elementy Δ są przepisywaniem reguł z węzłów, których korzenie potomne są stanami, do węzłów, których korzenie są stanami. W ten sposób stan węzła jest dedukowany ze stanów jego dzieci.

Dla n =0, to znaczy dla stałego symbolu f , powyższa definicja reguły przejścia brzmi f () → q ( f ()); często dla wygody pomija się puste nawiasy: fq ( f ). Ponieważ te reguły przejścia dla stałych symboli (liści) nie wymagają stanu, nie są potrzebne żadne jawnie zdefiniowane stany początkowe. Automat drzewa od dołu do góry jest uruchamiany na termie podstawowym nad F , zaczynając od wszystkich liści jednocześnie i poruszając się w górę, wiążąc stan biegu z Q z każdym podterminem. Termin jest akceptowany, jeśli jego pierwiastek jest powiązany ze stanem akceptującym z Q f .

Odgórne skończony automat drzewa przez F, definiuje się jako krotka ( Q , F , P ı , ó), z dwiema różnicami w oddolnym drzewa automatów. Po pierwsze, Q iQ , zbiór stanów początkowych, zastępuje Q f ; po drugie, jego reguły przejścia są zorientowane odwrotnie: q ( f ( x 1 ,..., x n )) → f ( q 1 ( x 1 ),..., q n ( x n )), dla n - ary fF , q , q iQ , oraz x i zmienne oznaczające poddrzewa. Oznacza to, że członkowie Δ przepisują tutaj reguły od węzłów, których pierwiastki są stanami, na węzły, których pierwiastki potomne są stanami. Automat zstępujący zaczyna w niektórych stanach początkowych u podstawy i przesuwa się w dół wzdłuż gałęzi drzewa, wiążąc indukcyjnie po biegu stan z każdym podczłonem. Drzewo jest akceptowane, jeśli każdą gałąź można przejść w ten sposób.

Automat drzewny nazywamy deterministycznym (w skrócie DFTA ) jeśli żadne dwie reguły z Δ nie mają tej samej lewej strony; w przeciwnym razie nazywa się to niedeterministycznym ( NFTA ). Niedeterministyczne automaty drzewa top-down mają taką samą moc ekspresyjną jak niedeterministyczne automaty bottom-up; reguły przejścia są po prostu odwrócone, a stany końcowe stają się stanami początkowymi.

W przeciwieństwie do tego, automaty deterministyczne drzewa zstępującego są słabsze niż ich odpowiedniki typu bottom-up, ponieważ w automacie deterministycznym drzewa żadne dwie reguły przejścia nie mają tej samej lewej strony. W przypadku automatów drzewnych reguły przejścia są regułami przepisywania; a dla odgórnych, lewa strona będzie węzłami nadrzędnymi. W konsekwencji deterministyczny automat drzewa zstępującego będzie mógł testować tylko te właściwości drzewa, które są prawdziwe we wszystkich gałęziach, ponieważ wybór stanu do zapisu w każdej gałęzi podrzędnej jest określany w węźle nadrzędnym, bez znajomości zawartości gałęzi podrzędnych .

Przykłady

Automat oddolny akceptujący listy logiczne

Stosując kolorowanie w celu rozróżnienia członków F i Q oraz używając alfabetu rangowanego F ={ false , true , nil , cons (.,.) }, gdzie con ma arity 2, a wszystkie inne symbole mają arity 0, drzewo od dołu do góry automat akceptujący zbiór wszystkich skończonych list wartości logicznych można zdefiniować jako ( Q , F , Q f , Δ ) gdzie Q ={ Bool , BList } , Q f ={ BList } i Δ składający się z reguł

fałszywe Bool ( fałsz ) (1),
prawda Bool ( prawda ) (2),
zero Lista BList ( zero ) (3) i
minusy ( Bool (x 1 ), BList (x 2 ) ) BList ( minusy (x 1 ,x 2 ))       (4).

W tym przykładzie reguły można rozumieć intuicyjnie jako przypisywanie każdemu terminowi jego typu w sposób oddolny; Np. reguła (4) może być odczytana jako "Termin minusy ( x 1 , x 2 ) ma typ BList , pod warunkiem, że x 1 i x 2 mają odpowiednio typ Bool i BList ". Akceptujący przykładowy przebieg to

minusy ( fałszywy , minusy ( prawda , zero ))
minusy ( fałszywy , minusy ( prawda , Lista BList ( zero ) )) przez (3)
minusy ( fałszywy , minusy ( Bool ( prawda ), Lista BList ( zero ) )) przez (2)
minusy ( fałszywy , Lista BList ( wady ( prawda , zero ))) przez (4)
minusy ( Bool ( fałsz ), Lista BList ( wady ( prawda , zero ))) przez (1)
Lista BList ( wady ( fałszywy , minusy ( prawda , zero )))       do (4), akceptowane.

Por. wyprowadzenie tego samego terminu z gramatyki drzewa regularnego odpowiadającego automatowi, pokazanej w Gramatyka drzewa regularnego#Przykłady .

Odrzucający przykładowy przebieg to

minusy ( fałszywy , prawda )
minusy ( fałszywy , Bool ( prawda ) ) przez (1)
minusy ( Bool ( fałsz ), Bool ( prawda ) )       do (2), nie stosuje się dalszych zasad.

Intuicyjnie odpowiada to terminowi wady ( false , true ), który nie jest dobrze wpisany.

Automat odgórny przyjmujący wielokrotności 3 w notacji binarnej

(A) (B) (C) (D)

Reguły gramatyki ciągów

Przejścia automatu strunowego

Automatyczne przejścia drzewa

Zasady gramatyczne drzewa
0
1
2
3
4
5
6
S 0 ε
S 0 0 S 0
S 0 1 S 1
S 1 0 S 2
S 1 1 S 0
S 2 0 S 1
S 2 1 S 2
 
( S 0 , 0 ) = S 0
δ( S 0 , 1 ) = S 1
δ( S 1 , 0 ) = S 2
δ( S 1 , 1 ) = S 0
δ( S 2 , 0 ) = S 1
δ( S 2 , 1 ) = S 2
S 0 ( zero ) zero
S 0 ( 0 (x)) 0 ( S 0 (x))
S 0 ( 1 (x)) 1 ( S 1 (x))
S 1 ( 0 (x)) 0 ( S 2 (x))
S 1 ( 1 (x)) 1 ( S 0 (x))
S 2 ( 0 (x)) 0 ( S 1 (x))
S 2 ( 1 (x)) 1 ( S 2 (x))
S 0 zero
S 0 0 ( S 0 )
S 0 1 ( S 1 )
S 1 0 ( S 2 )
S 1 1 ( S 0 )
S 2 0 ( S 1 )
S 2 1 ( S 2 )
Deterministyczny automat skończony (strunowy) akceptujący wielokrotności 3 w notacji binarnej

Używając tego samego kolorowania, co powyżej, ten przykład pokazuje, jak automaty drzewne uogólniają zwykłe automaty łańcuchowe. Pokazany na rysunku deterministyczny automat skończony przyjmuje wszystkie ciągi cyfr binarnych, które oznaczają wielokrotność 3. Korzystając z pojęć z Deterministyczny automat skończony#Formalna definicja , jest on zdefiniowany przez:

  • zbiór Q stanów to { S 0 , S 1 , S 2 },
  • alfabet wejściowy to { 0 , 1 },
  • stan początkowy to S 0 ,
  • zbiorem stanów końcowych jest { S 0 }, a
  • przejścia są takie, jak pokazano w kolumnie (B) tabeli.

W otoczeniu drzew automatu, alfabet wejściowy zostanie zmieniony tak, że symbole 0 i 1 są zarówno jednoskładnikowa, a sygnalnych symbol, powiedzmy zero służy do liści drzew. Na przykład ciąg binarny „ 110 ” w ustawieniu automatu strunowego odpowiada terminowi „ 1 ( 1 ( 0 ( nil )))” w ustawieniu automatu drzewnego; w ten sposób łańcuchy można uogólnić na drzewa lub terminy. Automat odgórnego drzewa skończonego przyjmujący zbiór wszystkich terminów odpowiadający wielokrotności 3 w notacji ciągu binarnego jest następnie definiowany przez:

  • zbiór Q stanów jest nadal { S 0 , S 1 , S 2 },
  • uszeregowany alfabet wejściowy to { 0 , 1 , nil }, z Arity ( 0 )= Arity ( 1 )=1 i Arity ( nil )=0, jak wyjaśniono,
  • zbiorem stanów początkowych jest { S 0 }, a
  • przejścia są takie, jak pokazano w kolumnie (C) tabeli.

Na przykład drzewo " 1 ( 1 ( 0 ( nil )))" jest akceptowane przez następujące uruchomienie automatu drzewnego:

S 0 ( 1 ( 1 ( 0 ( zero ))))
1 ( S 1 ( 1 ( 0 ( zero )))) o 2
1 ( 1 ( S 0 ( 0 ( zero )))) o 4
1 ( 1 ( 0 ( S 0 ( zero )))) o 1
1 ( 1 ( 0 ( zero )))       o 0

Natomiast wyrażenie " 1 ( 0 ( nil ))" prowadzi do następującego nieakceptującego przebiegu automatu:

S 0 ( 1 ( 0 ( zero )))
1 ( S 1 ( 0 ( zero )))) o 2
1 ( 0 ( S 2 ( zero ))))       o 3, nie stosuje się dalszych zasad

Ponieważ nie ma innych stanów początkowych niż S 0, od których można uruchomić automat, termin „ 1 ( 0 ( nil ))” nie jest akceptowany przez automat drzewa.

Dla celów porównawczych tabela podaje w kolumnach (A) i (D) (prawą) gramatykę regularną (stringową) , oraz gramatykę drzewa regularnego , z których każda akceptuje ten sam język jako odpowiednik automatu.

Nieruchomości

Rozpoznawalność

Dla automatu oddolnego, termin podstawowy t (tj. drzewo) jest akceptowany, jeśli istnieje redukcja, która zaczyna się od t i kończy na q ( t ), gdzie q jest stanem końcowym. Dla automatu zstępującego, termin podstawowy t jest akceptowany, jeśli istnieje redukcja, która zaczyna się od q ( t ) i kończy na t , gdzie q jest stanem początkowym.

Językiem drzewo L ( ) przyjęte lub uznane przez drzewa automatu A jest zbiorem wszystkich warunkach gruntowych zaakceptowanych przez A . Zbiór terminów podstawowych jest rozpoznawalny, jeśli istnieje automat drzewa, który go akceptuje.

Homomorfizm drzewa liniowego (czyli z zachowaniem aryczności) zachowuje rozpoznawalność.

Kompletność i redukcja

Niedeterministyczny automat drzewa skończonego jest kompletny, jeśli istnieje przynajmniej jedna reguła przejścia dostępna dla każdej możliwej kombinacji symbol-stan. Stan q jest dostępny, jeśli istnieje termin podstawowy t taki, że istnieje redukcja z t do q ( t ). NFTA ulega skróceniu, jeśli wszystkie jego stany są dostępne.

Lemat pompowania

Każdy wystarczająco duży człon podstawowy t w rozpoznawalnym języku drzewa L może być w pionie podzielony na trzy części tak, że arbitralne powtórzenie („pompowanie”) części środkowej utrzymuje wynikowy człon w L .

Dla języka wszystkich skończonych list wartości logicznych z powyższego przykładu, wszystkie wyrazy poza limitem wysokości k =2 mogą być pompowane, ponieważ muszą zawierać wystąpienie cons . Na przykład,

minusy ( fałszywe , minusy ( prawda , zero ) ) ,
minusy ( fałszywe , minusy ( fałszywe , minusy ( prawda , zero ) )) ,
minusy ( fałszywe , minusy ( fałszywe , minusy ( fałszywe , minusy ( prawda , zero ) ))) , ...

wszyscy należą do tego języka.

Zamknięcie

Klasa rozpoznawalnych języków drzewa jest zamknięta pod sumą, pod komplementacją i pod przecięciem.

Twierdzenie Myhilla-Nerodea

Kongruencja na zbiorze wszystkich drzew nad alfabetem rangowanym F jest relacją równoważności taką, że u 1v 1 i ... i u nv n implikuje f ( u 1 ,..., u n ) ≡ f ( v 1 , ..., V n ), dla każdej fF . Jest indeksem skończonym, jeśli liczba jego klas równoważności jest skończona.

Dla danego języka drzewa L , kongruencja może być zdefiniowana przez uL v jeśli C [ u ] ∈ LC [ v ] ∈ L dla każdego kontekstu C .

Twierdzenie Myhilla-Nerode'a dla automatów drzewnych stwierdza, że ​​następujące trzy zdania są równoważne:

  1. L to rozpoznawalny język drzewa
  2. L jest sumą niektórych klas równoważności kongruencji o skończonym indeksie
  3. relacja ≡ L jest kongruencją o skończonym indeksie

Zobacz też

Uwagi

Bibliografia

  • Wspólny, Hubert; Daucheta, Maxa; Gilleron, Remi; Jacquemard, Florent; Lugiez, Denis; Loding, Christof; Tison, Sophie; Tommasi, Marc (listopad 2008). Techniki i zastosowania automatów drzewnych (PDF) . Pobrano 11 lutego 2014 .
  • Hosoya, Haruo (4 listopada 2010). Podstawy przetwarzania XML: podejście automatyzujące drzewo . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-1-139-49236-2.

Linki zewnętrzne

Realizacje

  • Grappa - rankingowe i nierankingowe biblioteki automatów drzewa (OCaml)
  • Timbuk - narzędzia do analizy osiągalności i obliczeń automatów drzew (OCaml)
  • LETHAL - biblioteka do pracy z automatami drzew i żywopłotów skończonych (Java)
  • Biblioteka automatów drzewa sprawdzanego maszynowo (Isabelle [OCaml, SML, Haskell])
  • VATA - biblioteka do efektywnego manipulowania niedeterministycznymi automatami drzewnymi (C++)