Výška hvězdy - Star height
v teoretická informatika, přesněji v teorii formální jazyky, výška hvězdy je měřítkem strukturální složitosti regulární výrazy a běžné jazyky. Výška hvězdy pravidelného výraz se rovná maximální hloubce vnoření hvězd objevujících se v tomto výrazu. Výška hvězdy pravidelného Jazyk je nejmenší výška hvězd ze všech regulárních výrazů pro daný jazyk. Koncept výšky hvězd byl poprvé definován a studován Egganem (1963).
Formální definice
Více formálně, výška hvězdy a regulární výrazE přes konečnou abeceda A je indukčně definována takto:
- , , a pro všechny symboly abecedy A v A.
Tady, je speciální regulární výraz označující prázdnou množinu a ε speciální regulární výraz označující prázdné slovo; E a F jsou libovolné regulární výrazy.
Výška hvězdy h(L) běžného jazyka L je definována jako minimální výška hvězdy mezi všemi regulárními výrazy představujícími LIntuice je zde, že pokud jazyk L má velkou výšku hvězdy, pak je v jistém smyslu inherentně složitá, protože ji nelze popsat pomocí „snadného“ regulárního výrazu nízké výšky hvězdy.
Příklady
Zatímco výpočet výšky hvězdy v regulárním výrazu je snadný, určení výšky hvězdy v jazyce může být někdy složité. Pro ilustraci, regulární výraz
přes abecedu A = {a, b}má výšku hvězdy 2. Popsaný jazyk je však pouze množina všech slov končících znakem A: jazyk tedy lze popsat i výrazem
což je pouze výška hvězdy 1. Abychom dokázali, že tento jazyk skutečně má výšku hvězdy 1, je třeba ještě vyloučit, že by to bylo možné popsat regularepresí nižší výšky hvězd. V našem příkladu to lze provést nepřímým důkazem: Jeden dokazuje, že jazyk výšky hvězdy 0 obsahuje pouze konečně mnoho slov. Vzhledem k tomu, že uvažovaný jazyk je nekonečný, nemůže mít výšku hvězdy 0.
Výška hvězdy a skupinový jazyk je vypočítatelný: například výška hvězdičky jazyka nad {A,b} ve kterém je počet výskytů A a b jsou shodné modulo 2n je n.[1]
Egganova věta
Ve své klíčové studii o výšce hvězd pravidelných jazyků Eggan (1963) navázal vztah mezi teoriemi regulárních výrazů, konečných automatů a řízené grafy. V následujících letech se tento vztah stal známým jako Egganova větasrov. Sakarovitch (2009). Připomínáme si několik konceptů z teorie grafů a teorie automatů.
V teorii grafů je hodnost cyklu r(G) a řízený graf (digraf) G = (PROTI, E) je indukčně definována takto:
- Li G je acyklický, pak r(G) = 0. To platí zejména, pokud G je prázdný.
- Li G je silně propojený a E je tedy neprázdné
- kde je digraf vyplývající z vypuštění vrcholu proti a všechny hrany začínající nebo končící na proti.
- Li G tedy není silně propojen r(G) se rovná maximálnímu pořadí cyklu mezi všemi silně propojenými složkami G.
V teorii automatů, a nedeterministický konečný automat s tahy ε (ε-NFA) je definována jako a 5-tice, (Q, Σ, δ, q0, F), skládající se z
- konečný soubor států Q
- konečná sada vstupní symboly Σ
- sada označených okrajů δ, označované jako přechodový vztah: Q × (Σ ∪ {ε}) × Q. Zde ε označuje prázdné slovo.
- an počáteční Stát q0 ∈ Q
- soubor států F rozlišovat jako přijímající státy F ⊆ Q.
Slovo w ∈ Σ* je akceptováno ε-NFA, pokud existuje a směrovaná cesta z původního stavu q0 do nějakého konečného stavu v F pomocí hran z δ, tak, že zřetězení všech štítků navštívených podél cesty přináší slovo w. Sada všech slov přes Σ* přijímaný automatem je Jazyk přijato automatem A.
Když mluvíme o digrafických vlastnostech nedeterministického konečného automatu A se stavovou sadou Q, přirozeně oslovujeme digraf s množinou vrcholů Q indukované jeho přechodovým vztahem. Nyní je věta uvedena následovně.
- Egganova věta: Výška hvězdy běžného jazyka L rovná se minimum hodnost cyklu mezi všemi nedeterministické konečné automaty s tahy ε přijímání L.
Důkazy této věty jsou dány Eggan (1963) a v poslední době také Sakarovitch (2009).
Zobecněná výška hvězdy
Výše uvedená definice předpokládá, že regulární výrazy jsou vytvářeny z prvků abecedy Apoužívající pouze standardní operátory nastavit unii, zřetězení, a Kleene hvězda. Zobecněné regulární výrazy jsou definovány stejně jako regulární výrazy, ale zde také sada doplňků operátor je povolen (doplněk je vždy brán s ohledem na množinu všech slov nad A). Změníme-li definici tak, aby užívání doplňků nezvýšilo výšku hvězdy, to znamená,
můžeme definovat zobecněná výška hvězdy běžného jazyka L jako minimální výška hvězdy mezi všemi zobecněný regulární výrazy představující L.
Všimněte si, že i když je okamžité, že jazyk (běžné) výšky hvězdy 0 může obsahovat pouze konečně mnoho slov, existuje nekonečné množství jazyků, které mají zobecněnou výšku hvězdy 0. Například regulární výraz
které jsme viděli ve výše uvedeném příkladu, lze ekvivalentně popsat zobecněným regulárním výrazem
- ,
protože doplněk prázdné množiny je přesně množina všech slov A. Tedy množina všech slov nad abecedou A končící v dopise A má výšku hvězdy jedna, zatímco její zobecněná výška hvězdy se rovná nule.
Rovněž se nazývají jazyky zobecněné nulové výšky hvězd jazyky bez hvězd. Je možné ukázat, že jazyk L je bez hvězd, jen když je syntaktický monoid je neperiodické (Schützenberger (1965) ).
Viz také
Reference
- ^ Sakarovitch (2009) str. 342
- Berstel, Jean; Reutenauer, Christophe (2011), Nekomutativní racionální řady s aplikacemiEncyklopedie matematiky a její aplikace 137, Cambridge: Cambridge University Press, ISBN 978-0-521-19022-0, Zbl 1250.68007
- Cohen, Rina S. (1971), „Techniky pro stanovení výšky hvězdy pravidelných souborů“, Teorie výpočetních systémů, 5 (2): 97–114, doi:10.1007 / BF01702866, ISSN 1432-4350, Zbl 0218.94028
- Cohen, Rina S .; Brzozowski, J.A. (1970), "Obecné vlastnosti výšky hvězdy pravidelných událostí", 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), „Přechodové grafy a výška hvězd pravidelných událostí“, Michigan Mathematical Journal, 10 (4): 385–397, doi:10,1307 / mmj / 1028998975, Zbl 0173.01504
- Sakarovitch, Jacques (2009), Základy teorie automatůPřeložil Reuben Thomas z Cambridge z francouzštiny: Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177
- Salomaa, Arto (1981), Klenoty teorie formálního jazyka, Rockville, Maryland: Computer Science Press, ISBN 978-0-914894-69-8, Zbl 0487.68064
- Schützenberger, M.P. (1965), „O konečných monoidech majících pouze triviální podskupiny“, Informace a kontrola, 8 (2): 190–194, doi:10.1016 / S0019-9958 (65) 90108-7, ISSN 0019-9958, Zbl 0131.02001