Czy istnieje jakaś znana „ładna” hierarchia (może być skończona) w klasie zwykłych języków ? Przyjemnie tutaj, klasy w każdej hierarchii przechwytują różną ekspresję / siłę / złożoność. Przynależność do każdej klasy jest „ładnie” wykazana przez niektóre elementy (w przeciwieństwie do problemu wysokości gwiazdy, który może być problematyczny).
Dziękuję Ci!
automata-theory
regular-language
regular-expressions
raja.damanik
źródło
źródło
Odpowiedzi:
Oto lista kilku hierarchii interesów, z których niektóre zostały już wspomniane w innych odpowiedziach.
Język jest oznaczony produkt z L 0 , L 1 , ... , L n jeśli L = L 0 1 L 1 ⋯ n L n do niektórych liter 1 , ... , n . Hierarchie konkatenacji są definiowane przez naprzemienne operacje boolowskie i operacje wielomianowe (= związek i oznaczony produkt). Hierarchia Straubing-Thérien (punkt początkowy { ∅ , A ∗ } )L L0,L1,…,Ln L=L0a1L1⋯anLn a1,…,an {∅,A∗}) i hierarchia głębokości kropek (punkt początkowy są tego typu, ale można wziąć inne punkty początkowe, w szczególności języki grupowe (języki akceptowane przez automat permutacyjny).{ ∅ , { 1 } , A+, A∗} )
Ogólny wzór polega na zliczeniu minimalnej liczby zagnieżdżonych gwiazd potrzebnych do wyrażenia języka zaczynającego się od liter, ale możliwych jest kilka wariantów, w zależności od podstawowych operatorów, na które zezwolisz. Jeśli zezwalasz tylko na łączenie i iloczyn, definiujesz ograniczoną wysokość gwiazdy, jeśli zezwalasz na łączenie, dopełnianie i iloczyn, definiujesz (uogólnioną) wysokość gwiazdy, a jeśli zezwalasz na łączenie, przecięcie i iloczyn, definiujesz pośrednią wysokość gwiazdy . Istnieją języki ograniczonej gwiazdy dla każdego n i dalej mogą skutecznie obliczyć wysokość gwiazdy dla danego języka regularnego. Dla wysokości gwiazdy decyduje wysokość gwiazdy 0 ( języki bez gwiazd ), istnieją języki wysokości gwiazdyn n 0 1 , ale żaden język o wysokości gwiazdy jest znany! Nie jest znany żaden wynik na pośredniej wysokości gwiazdy. Zobacz ten papier na przegląd.2)
Istnieje wiele z nich, ale jednym z najważniejszych z nich jest tzw hierarchia. Wzór mówi się Σ n -formula jeśli jest to równoważne formuły postaci Q ( x 1 , . . . , X K ) φ gdzie φ jest wolny i kwantyfikator Q ( x 1 , . . . , Bloki kwantyfikatorów, tak że pierwszy blok zawiera tylko kwantyfikatory egzystencjalne (zauważ, że ten pierwszy blok może być pusty), kwantyfikatory uniwersalne drugiego bloku itp. Podobnie, jeśli QΣn Σn Q(x1,...,xk)φ φ jest sekwencjąQ(x1,...,xk) n jest utworzona z n naprzemienne bloki kwantyfikatorów zaczynające się od bloku uniwersalnych kwantyfikatorów (które znów mogą być puste), mówimy, że φ jestformułą Π n . Oznacz przez Σ n (odpowiednio. Π n ) klasę języków, które można zdefiniować za pomocąformuły Σ n (odpowiednio. A ΠQ(x1,...,xk) n φ Πn Σn Πn Σn Πn formula) i przez logiczne zamknięcie Σ n- języków. Na koniec niech Δ n = Σ n ∩ Π n . Ogólny obraz wygląda tak
: Oczywiście trzeba określić podpis. Zwykle jest orzecznikiem dla każdej litery (i a x środków nie jest list w pozycji x w słowie). Następnie można dodać symbol binarny <BΣn Σn Δn=Σn∩Πn a ax a x < (odpowiednią hierarchią jest hierarchia Straubinga-Thériena), a także symbol zastępczy (odpowiednią hierarchią jest hierarchia z głębokością kropek). Inne możliwości obejmują: źródłowe, do zliczania modulo n itp zobaczy tegopapierudla przeglądu.Mod n
Ogólny wzorzec (który nie jest specyficzny dla zwykłych języków) wynika z Hausdorffa. Niech będzie klasą języków zawierających pusty zbiór i pełny zbiór i zamkniętych pod skończonym przecięciem i skończonym zjednoczeniem. Niech D n ( L ) będzie klasą wszystkich języków w postaci X = X 1 - X 2 + ⋯ ± X n, gdzie X i ∈ L i X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ X n D nL Dn(L)
Wynik Krohna-Rhodesa (1966) stwierdza, że każdy DFA może być symulowany przez kaskadę automatów resetujących (zwanych także flip-flop) i automatów, których półgrupami przejścia są grupy skończone. Złożoność grupowa języka to najmniejsza liczba grup zaangażowanych w taki rozkład minimalnego DFA języka. Języki złożoności są dokładnie językami bez gwiazd i istnieją języki o dowolnej złożoności. Jednak nie jest znana skuteczna charakterystyka języków złożoności 1 .0 1
Punktem wyjścia jest ładny artykuł który pokazuje w szczególności, że klasa A C 0 ∩ R e g jest rozstrzygalna. Niech A C C ( q ) = { L ⊆ { 0 , 1 } ∗ ∣ L ⩽ A C 0 M O D q } , gdzie M O D q = { u ∈ { ∣ | u |[1] AC0∩Reg ACC(q)={L⊆{0,1}∗∣L⩽AC0MODq} . Jeżeli q dzieli q ′ , to A C C ( q ) ⊆ A C C ( q ′ ) . Interesujące pytanie jest, aby wiedzieć, czy C C ( Q ) ∩ R e g jest rozstrzygalne dla każdego q .MODq={u∈{0,1}∗∣|u|1≡0modq} q q′ ACC(q)⊆ACC(q′) ACC(q)∩Reg q
źródło
Rozszerzanie komentarza: naturalna hierarchia jest indukowana przez liczbę stanów DFA.
Możemy zdefiniowaćL.n= { L ∣ istnieje n-stany DFA D st L ( D ) = L }
(D = { Q , Σ , δ,q0,F} , |Q|=n )
ClearlyLn⊆Ln+1 (simply use dead states)
To show the proper inclusionLn⊊Ln+1 we can simply pick the language: Ln+1={ai∣i≥n}∈Ln+1
Very informally: the (minimum) DFA that recognizes{ai∣i≥n} must be a "state chain" of length n+1 : q0→aq1→a...→aqn , F={qn} and qn→aqn (qn has a self-loop). So n+1 states are enough to accept Ln+1 . But every accepting path from q0 to a final state qf which is strictly shorter than n+1 must accept some ai with i<n which doesn't belong to Ln+1 , so a DFA with n or fewer states cannot accept Ln+1 .
źródło
I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract):
Guillaume Bonfante, Florian Deloup: The genus of regular languages.
From the abstract: The article defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, a FSA can be seen as a graph for which the notion of genus arises. At the same time, a FSA has a semantics via its underlying language. It is then natural to make a connection between the languages and the notion of genus. After we introduce and justify the the notion of the genus for regular languages, [...] we build regular languages of arbitrary large genus: the notion of genus defines a proper hierarchy of regular languages.
źródło
There are several natural hierarchies for regular languages of infinite words, that convey a notion of "complexity of the language", for instance:
These hierarchies can be generalised for regular languages of infinite trees, for which new hierarchies appear, see for instance this answer.
źródło