Omega jazyk - Omega language - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

An ω -Jazyk je soubor nekonečně dlouhých sekvencí symboly.

Formální definice

Nechť Σ je sada symbolů (nemusí být nutně konečná). Podle standardní definice z formální jazyk teorie, Σ^* je množina všech konečný slova přes Σ. Každé konečné slovo má délku, což je přirozené číslo. Dostal slovo w délky n, w lze zobrazit jako funkci z množiny {0,1, ...,n-1} → Σ, s hodnotou na i dávat symbol na pozici i. Na nekonečná slova nebo ω-slova lze také pohlížet jako na funkce z ${ displaystyle mathbb {N}}$ do Σ. Množina všech nekonečných slov nad Σ je označena Σ^ω. Sada všech konečných a nekonečná slova nad Σ je někdy psána Σ^∞.

Tedy jazyk ω L přes Σ je podmnožina z Σ^ω.

Operace

Některé běžné operace definované v jazycích ω jsou:

• Křižovatka a spojení. Vzhledem k ω-jazykům L a M, oba L ∪ M a L ∩ M jsou ω-jazyky.
• Zřetězení vlevo. Nechat L být jazykem ω a K. být jazykem pouze konečných slov. Pak K. lze zřetězit vlevo pouze na L čímž získáme nový jazyk ω KL.
• Omega (nekonečná iterace). Jak naznačuje zápis, operace (${ displaystyle cdot}$)^ω je nekonečná verze Kleene hvězda operátor v jazycích konečné délky. Vzhledem k formálnímu jazyku L, L^ω je jazyk ω všech nekonečných posloupností slov z L; ve funkčním zobrazení všech funkcí ${ displaystyle mathbb {N}}$→L.
• Předpony. Nechat w být ω-slovo. Pak formální jazyk Pref (w) obsahuje všechny konečný předpona z w.
• Omezit. Vzhledem k jazyku konečné délky L, ω-slovo w je v omezit z L právě když Pref (w) ∩ L je nekonečný soubor. Jinými slovy, pro libovolně velké přirozené číslo n, vždy je možné vybrat nějaké slovo L, jehož délka je větší než n, a což je předpona w. Limitní operace zapnuta L lze psát L^δ nebo ${ displaystyle { vec {L}}}$.

Vzdálenost mezi ω slovy

Sada Σ^ω lze udělat z metrický prostor podle definice metrický ${ displaystyle d: Sigma ^ { omega} krát Sigma ^ { omega} rightarrow mathbb {R}}$ tak jako:

${ displaystyle d (w, v) = inf {2 ^ {- | x |}: x in Sigma ^ {*} { text {and}} x in { text {pref} } (w) cap { text {Pref}} (v) }}$

kde |X| je interpretován jako „délka X"(počet symbolů v X), a inf je infimum přes sady reálná čísla. Li ${ displaystyle w = v}$ pak neexistuje nejdelší předpona X a tak ${ displaystyle d (w, v) = 0}$. Symetrie je jasná. Transitivita vyplývá ze skutečnosti, že pokud w a proti mít maximální sdílenou předponu délky m a proti a u mít maximální sdílenou předponu délky n pak první ${ displaystyle min {m, n }}$ znaky w a u musí to být stejné ${ Displaystyle d (w, u) leq 2 ^ {- min {m, n }} leq 2 ^ {- m} +2 ^ {- n} = d (w, v) + d ( v, u)}$. Proto d je metrika.

Důležité podtřídy

Nejpoužívanější podtřídou jazyků ω je sada ω-běžné jazyky, které těží z užitečné vlastnosti, že je lze rozpoznat pomocí Büchi automaty. Tak rozhodovací problém členství v ω-regulárním jazyce je rozhodnutelné pomocí Büchiho automatu a jeho výpočet je poměrně přímočarý.

Pokud je jazyk Σ napájecí sada množiny (nazývaných „atomové výroky“), pak jazyk ω je a lineární časová vlastnost, které jsou studovány v kontrola modelu.

Bibliografie

• Perrin, D. a Pin, J. E. "Nekonečná slova: automaty, poloskupiny, logika a hry Čistá a aplikovaná matematika, svazek 141, Elsevier, 2004.
• Staiger, L. "ω-jazyky ". V G. Rozenberg a A. Salomaa, redaktoři, Příručka formálních jazyků, Svazek 3, strany 339-387. Springer-Verlag, Berlín, 1997.
• Thomas, W. „Automaty na nekonečných objektech“. v Jan van Leeuwen, editor, Příručka teoretické informatiky, Svazek B: Formální modely a sémantika, strany 133-192. Elsevier Science Publishers, Amsterdam, 1990.