Výška iterace jazyka

V teoretické informatice , přesněji v teorii formálních jazyků , je iterační výška  měřítkem strukturní složitosti regulárních výrazů  - iterační výška regulárního výrazu je rovna maximální hloubce vnoření hvězdiček přítomných v regulárním výrazu. výraz. Pojem iterační výšky poprvé představil a studoval Eggan (1963).

Formální definice

Formálně je iterační výška regulárního výrazu E přes konečnou abecedu A definována induktivně takto:

Zde znamená prázdnou množinu, ε znamená prázdný řetězec a E a F  jsou libovolné regulární výrazy.

Iterační výška h ( L ) regulárního jazyka L je definována jako minimální iterační výška všech regulárních výrazů reprezentujících L . Intuitivně, pokud má jazyk L vysokou iterační výšku, je sám o sobě složitý, protože jej nelze popsat pomocí „jednoduchých“ regulárních výrazů s nízkou iterační výškou.

Příklady

Zatímco výpočet výšky iterace regulárního výrazu je jednoduchý, definice výšky iterace jazyka může být někdy matoucí. Jako příklad regulární výraz

nad abecedou A = {a, b} má iterační výšku 2. Popisovaný jazyk je však množinou všech slov končících na a . Stejný jazyk lze popsat pomocí výrazu

,

jehož iterační výška je pouze 1. Abychom dokázali, že iterační výška jazyka je 1, musíme vyloučit možnost popsat jazyk regulárním výrazem s nižší iterační výškou. To lze například provést nepřímo důkazem, že jazyk s výškou iterace 0 obsahuje pouze konečný počet slov. Protože náš jazyk je nekonečný, nemůže mít iterační výšku 0.

Iterační výška jazyka skupiny je vyčíslitelná. Například výška jazykové iterace přes { a , b }, ve které je počet výskytů a a b shodný modulo 2 n je n [1] .

Egganův teorém

Ve svých klíčových studiích o iterační výšce regulárních jazyků Eggan [2] prokázal spojení mezi teorií regulárních výrazů, teorií konečných automatů a orientovanými grafy . Následně toto spojení vešlo ve známost jako Egganův teorém [3] . Připomínáme některé pojmy z teorie grafů a teorie automatů .

V teorii grafů je cyklická hodnost r ( G ) orientovaného grafu (digrafu) G  = ( V ,  E ) definována induktivně takto:

 kde G - v je digraf získaný odstraněním vrcholu v a všech oblouků, které začínají nebo končí na v.

V teorii automatů je nedeterministický konečný automat s ε-přechody (ε-NFA) definován jako n-tice ( Q , Σ, δ , q 0 , F ) skládající se z

Slovo w ∈ Σ * je akceptováno jako ε-NCF, pokud existuje orientovaný řetězec z počátečního stavu q 0 do nějakého konečného stavu F pomocí dig od δ tak, že zřetězení všech značek podél cesty tvoří slovo w . Množina všech slov nad Σ * akceptovaná automatem je jazyk akceptovaný automatem A .

Hovoříme-li o nedeterministickém konečném automatu A se stavovou množinou Q jako orientovaným grafem, máme přirozeně na mysli graf s vrcholovou množinou Q generovaný přechody. Nyní můžeme vyslovit větu.

Egganův teorém : Iterační výška regulárního jazyka L je rovna nejmenší cyklické řadě ze všech nedeterministických konečných automatů s ε-přechody přijímajícími jazyk L.

Důkaz této věty podal Eggan [2] a později Sakarovič [3] .

Zobecněný problém výšky iterace

Výše uvedená definice předpokládá, že regulární výraz je postaven na prvcích abecedy A a používá pouze standardní operace sjednocení množin , zřetězení a Kleeneův uzávěr . Zobecněný regulární výraz je definován jako regulární výraz, ale zahrnuje také operaci množinového doplňku (doplněk je vždy vztažen ke všem slovům nad A). Pokud předpokládáme, že použití výplně nezvýší výšku iterace, tzn

,

můžeme definovat výšku iterace zobecněného regulárního jazyka L jako minimální výšku iterace mezi všemi zobecněnými regulárními výrazy reprezentujícími jazyk L .

Všimněte si, že zatímco jazyky s nulovou (běžnou) výškou iterace obsahují konečný počet slov, existuje nekonečně mnoho jazyků s nulovou zobecněnou výškou iterace.

Příklad . Regulární výraz

který jsme viděli v příkladu výše, lze ekvivalentně přepsat jako zobecněný regulární výraz

,

protože doplňkem prázdné množiny jsou přesně všechna slova v abecedě A . Množina všech slov v abecedě A končících písmenem a má tedy iterační výšku jedna, zatímco zobecněná iterační výška je nula.

Jazyky s nulovou výškou iterace se nazývají jazyky bez hvězdiček . Lze ukázat, že jazyk L je jazykem bez hvězdiček právě tehdy, když jeho syntaktický monoid je aperiodický [4] .

Viz také

Poznámky

  1. ↑ Sakarovič, 2009 , str. 342.
  2. ↑ 12 Eggan , 1963 .
  3. ↑ 12. Sakarovič , 2009 .
  4. ↑ Schützenberger, 1965 .

Literatura