Wysokość gwiazdy

W informatyce teoretycznej , a dokładniej w teorii języków formalnych , wysokość gwiazdy jest miarą złożoności strukturalnej wyrażeń regularnych i języków regularnych . Wysokość gwiazdki wyrażenia regularnego jest równa maksymalnej głębokości zagnieżdżenia gwiazdek występujących w tym wyrażeniu. Wysokość gwiazdki języka regularnego to najmniejsza wysokość gwiazdki dowolnego wyrażenia regularnego dla tego języka. Pojęcie wysokości gwiazdy zostało po raz pierwszy zdefiniowane i zbadane przez Eggana (1963).

Definicja formalna

Bardziej formalnie, wysokość gwiazdy wyrażenia regularnego E nad skończonym alfabetem A jest indukcyjnie zdefiniowana w następujący sposób:

• ${\ Displaystyle \ textstyle h \ lewo (\ pusty zestaw \ po prawej) \, = \, 0}$ , ${\ Displaystyle \ textstyle h \ lewo (\ varepsilon \ po prawej) \, = \ , 0}$ i ${\ Displaystyle \ textstyle h \ lewo (a \ prawo) \, = \, 0}$ dla wszystkich symboli alfabetu a w A .
• ${\ Displaystyle \ textstyle h \ lewo (EF \ prawo) \, = \, h \ lewo (E \, \mid \,F\right)\,=\,\max \left(\,h(E),h(F)\,\right)}$
• ${\ Displaystyle \ textstyle h \ lewo (E ^ {*} \ prawo) \ = \, h (E) + 1.}$

Tutaj ${\ displaystyle \ scriptstyle \ emptyset}$ jest specjalnym wyrażeniem regularnym oznaczającym pusty zestaw i ε specjalnym oznaczającym puste słowo ; E i F są dowolnymi wyrażeniami regularnymi.

Wysokość gwiazdy h ( L ) języka regularnego L jest zdefiniowana jako minimalna wysokość gwiazdy spośród wszystkich wyrażeń regularnych reprezentujących L . Intuicja jest tutaj taka, że ​​jeśli język L ma dużą wysokość gwiazdy, to jest w pewnym sensie z natury złożony, ponieważ nie można go opisać za pomocą „łatwego” wyrażenia regularnego o małej wysokości gwiazdy.

Przykłady

Chociaż obliczenie wysokości gwiazdki w wyrażeniu regularnym jest łatwe, określenie wysokości gwiazdki w języku może być czasami trudne. Dla ilustracji wyrażenie regularne

${\ Displaystyle \ textstyle \ lewo (b \, \ środkowy \, aa ^ {*} b \ prawo) ^ {*} aa ^ {*}}$

nad alfabetem A = {a,b} ma wysokość gwiazdki 2. Jednak opisywany język jest tylko zbiorem wszystkich słów kończących się na a : więc język można również opisać wyrażeniem

${\ Displaystyle \ textstyle (a \ \ mid \, b) ^ {*} a}$

który ma tylko wysokość gwiazdy 1. Aby udowodnić, że ten język rzeczywiście ma wysokość gwiazdy 1, nadal trzeba wykluczyć, że można go opisać wyrażeniem regularnym o niższej wysokości gwiazdy. W naszym przykładzie można to zrobić za pomocą dowodu pośredniego: dowodzi się, że język o wysokości gwiazdy 0 zawiera tylko skończenie wiele słów. Ponieważ rozważany język jest nieskończony, nie może mieć wysokości gwiazdy 0.

Wysokość gwiazdy języka grupowego jest obliczalna: na przykład wysokość gwiazdy języka nad { a , b }, w którym liczba wystąpień aib jest przystająca modulo 2 ⁿ wynosi n .

Twierdzenie Eggana

Przykładowy automat rangi cyklu 1. Algorytm Kleene'a przekształca go w wyrażenie regularne a ^* b ^* ba (( a | b ) b ^* a |ε) ^* ( a | b ) b ^* | a ^* b ^* b , który ma wysokość gwiazdy 2. Zgodnie z twierdzeniem Eggana musi istnieć równoważne wyrażenie regularne o wysokości gwiazdy ≤1. W rzeczywistości a ^* b ( b | a ( a | b )) ^* opisuje ten sam język.

W swoim przełomowym badaniu wysokości gwiazd w językach regularnych Eggan (1963) ustalił związek między teorią wyrażeń regularnych, automatów skończonych i grafów skierowanych . W kolejnych latach zależność ta stała się znana jako twierdzenie Eggana , por. Sakarowicz (2009) . Przypomnijmy sobie kilka pojęć z teorii grafów i teorii automatów .

W teorii grafów ranga cyklu r ( G ) skierowanego grafu (digrafu) G = ( V , E ) jest indukcyjnie zdefiniowana w następujący sposób:

• Jeśli G jest acykliczne , to r ( G ) = 0 . Dotyczy to w szczególności przypadku, gdy G jest puste.
• Jeśli G jest silnie spójny , a E jest niepuste, to

 ${\ Displaystyle r (G) = 1 + \ min _ {v \ in V} r (Gv), \,}$ gdzie ${ \displaystyle Gv}$ to dwuznak wynikający z usunięcia wierzchołka v i wszystkich krawędzi zaczynających się lub kończących na v .

• Jeśli G nie jest silnie spójny, to r ( G ) jest równy maksymalnemu rządowi cyklu wśród wszystkich silnie połączonych składowych G .

W teorii automatów niedeterministyczny automat skończony z ε-przejściami (ε-NFA) jest definiowany jako 5-krotka , ( Q , Σ, δ , q ₀ , F ), składający się z

• skończony zbiór stanów Q
• skończony zbiór symboli wejściowych Σ
• zbiór oznaczonych krawędzi δ , określanych jako relacja przejścia : Q × (Σ ∪{ε}) × Q . Tutaj ε oznacza puste słowo .
• stan początkowy q ∈ Q _ ₀
• zbiór stanów F wyróżnionych jako stany akceptujące F ⊆ Q .

₀ Słowo w ∈ Σ ^* jest akceptowane przez ε-NFA, jeśli istnieje skierowana ścieżka od stanu początkowego q do pewnego stanu końcowego w F przy użyciu krawędzi z δ , taka że konkatenacja wszystkich etykiet odwiedzonych wzdłuż ścieżki daje słowo w . Zbiór wszystkich słów nad Σ ^* akceptowanych przez automat jest językiem akceptowanym przez automat A .

Mówiąc o własnościach digrafu niedeterministycznego automatu skończonego A ze zbiorem stanów Q , w naturalny sposób odnosimy się do digrafu o zbiorze wierzchołków Q indukowanym jego relacją przejścia. Teraz twierdzenie jest sformułowane w następujący sposób.

Twierdzenie Eggana : Wysokość gwiazdy języka regularnego L jest równa minimalnemu stopniowi cyklu wśród wszystkich niedeterministycznych automatów skończonych z przejściami ε akceptującymi L .

Dowody tego twierdzenia podaje Eggan (1963) , a ostatnio Sakarovitch (2009) .

Uogólniona wysokość gwiazdy

Powyższa definicja zakłada, że ​​wyrażenia regularne są budowane z elementów alfabetu A przy użyciu tylko standardowych operatorów set union , concatenation i Kleene star . Uogólnione wyrażenia regularne są definiowane tak samo jak wyrażenia regularne, ale tutaj również dozwolony jest operator dopełnienia zbioru (dopełnienie jest zawsze przyjmowane w odniesieniu do zbioru wszystkich słów nad A). Jeśli zmienimy definicję tak, że przyjmowanie dopełnień nie zwiększy wysokości gwiazdy, to znaczy:

${\ Displaystyle \ textstyle h \ lewo (E ^ {c} \ prawo) \ = \, h (E)}$

możemy zdefiniować uogólnioną wysokość gwiazdki języka regularnego L jako minimalną wysokość gwiazdki spośród wszystkich uogólnionych wyrażeń regularnych reprezentujących L . Otwartym problemem jest to , czy niektóre języki można wyrazić tylko za pomocą uogólnionej wysokości gwiazdy większej niż jeden: to jest uogólniony problem wysokości gwiazdy .

Zauważ, że chociaż jest oczywiste, że język o (zwykłej) wysokości gwiazdy 0 może zawierać tylko skończoną liczbę słów, istnieją nieskończone języki o uogólnionej wysokości gwiazdy 0. Na przykład wyrażenie regularne

${\ Displaystyle \ textstyle (a \ \ mid \, b) ^ {*} a,}$

co widzieliśmy w powyższym przykładzie, można równoważnie opisać uogólnionym wyrażeniem regularnym

${\ Displaystyle \ textstyle \ pusty zbiór ^ {c} a}$ ,

ponieważ dopełnieniem zbioru pustego jest właśnie zbiór wszystkich słów nad A . Zatem zbiór wszystkich słów z alfabetu A kończących się na literę a ma wysokość gwiazdy jeden, podczas gdy jego uogólniona wysokość gwiazdy jest równa zeru.

Języki o uogólnionej wysokości gwiazdy zerowej są również nazywane językami bezgwiezdnymi . Można wykazać, że język L jest pozbawiony gwiazdek wtedy i tylko wtedy, gdy jego monoid składniowy jest aperiodyczny ( Schützenberger (1965) ).

Zobacz też

• Problem z wysokością gwiazdy
• Uogólniony problem wysokości gwiazdy

•    Berstel, Jean; Reutenauer, Christophe (2011), Nieprzemienne szeregi wymierne z zastosowaniami , Encyklopedia matematyki i jej zastosowań, tom. 137, Cambridge: Cambridge University Press , ISBN 978-0-521-19022-0 , Zbl 1250.68007
•     Cohen, Rina S. (1971), „Techniki ustalania wysokości gwiazd regularnych zbiorów”, Theory of Computing Systems , 5 (2): 97–114, doi : 10.1007 / BF01702866 , ISSN 1432-4350 , S2CID 1970902 , Zbl 0218.94028
•    Cohen, Rina S.; Brzozowski, JA (1970), „Ogólne właściwości wysokości gwiazdy regularnych zdarzeń”, Journal of Computer and System Sciences , 4 (3): 260–280, doi : 10.1016 / S0022-0000 (70) 80024-1 , ISSN 0022 -0000 , Zbl 0245.94038
•   Eggan, Lawrence C. (1963), „Wykresy przejściowe i wysokość gwiazdy regularnych zdarzeń”, Michigan Mathematical Journal , 10 (4): 385–397, doi : 10,1307 / mmj / 1028998975 , Zbl 0173.01504
•    Sakarovitch, Jacques (2009), Elementy teorii automatów , przetłumaczone z francuskiego przez Reubena Thomasa, Cambridge: Cambridge University Press , ISBN 978-0-521-84425-3 , Zbl 1188.68177
•    Salomaa, Arto (1981), Klejnoty teorii języka formalnego , Rockville, Maryland: Computer Science Press, ISBN 978-0-914894-69-8 , Zbl 0487.68064
•    Schützenberger, MP (1965), „O skończonych monoidach mających tylko trywialne podgrupy”, Information and Control , 8 (2): 190–194, doi : 10.1016 / S0019-9958 (65) 90108-7 , ISSN 0019-9958 , Zbl 0131.02001