Nekonečné slovo - Profinite word
tento článek potřebuje další citace pro ověření.Květen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v matematika, přesněji v teorie formálního jazyka, jsou neúplná slova zobecněním pojmu konečná slova do kompletní topologický prostor. Tato představa umožňuje použití topologie studovat jazyky a konečný poloskupiny. Například profinitní slova se používají k alternativní charakterizaci algebraického pojmu a rozmanitost konečných poloskupin.
Definice
Nechat A an abeceda. Sada nekonečných slov A se skládá z dokončení metrického prostoru, jehož doménou je množina slov A. Vzdálenost použitá k definování metriky je dána pomocí pojmu oddělení slov. Tyto pojmy jsou nyní definovány.
Oddělení
Nechat M a N být monoidy a nechte str a q být prvky monoidu M. Nechat φ být morfismus monoidů z M na N. Říká se, že morfismus φ odděluje str a q -li . Například morfismus odeslání slova na paritu jeho délky odděluje slova ababa a abaa. Vskutku .
Říká se, že N odděluje str a q pokud existuje morfismus monoidů φ z M na N který odděluje str a q. Pomocí předchozího příkladu odděluje ababa a abaa. Obecněji, odděluje všechna slova, jejichž velikost není shodná modulo n. Obecně lze oddělit libovolná dvě odlišná slova pomocí monoidu, jehož prvky jsou faktory str plus nový prvek 0. Morphism vysílá předpony str pro sebe a všechno ostatní na 0.
Vzdálenost
Vzdálenost mezi dvěma odlišnými slovy str a q je definována jako inverzní k velikosti nejmenšího monoidu N oddělující str a q. Tedy vzdálenost ababa a abaa je . Vzdálenost str a sám je definován jako 0.
Tato vzdálenost d je ultrametrický, to znamená, . Dále to uspokojuje a Od jakýchkoli slov str lze oddělit od jakéhokoli jiného slova pomocí monoidu s | p | +1 prvky, kde | p | je délka str, z toho vyplývá, že vzdálenost mezi str a jakékoli jiné slovo je alespoň . Tedy topologie definovaná touto metrikou je oddělený.
Nekonečná topologie
Nekonečné dokončení , označeno , je dokončení množiny konečných slov ve vzdálenosti definované výše. Dokončení zachovává monoidní strukturu.
Topologie zapnuta je kompaktní[vyjasnit ].
Jakýkoli monoidní morfismus , s M konečnou lze jednoznačně rozšířit do morfismu a tento morfismus je rovnoměrně spojité[vyjasnit ]. Dále je nejméně topologický prostor s touto vlastností.
Nekonečné slovo
Ziskové slovo je prvkem . A profinite language is a set of profinite words. Každé konečné slovo je slovo v reálném čase. Nyní je uvedeno několik příkladů neomezených slov, která nejsou konečná.
Pro m jakékoli slovo, ať označit . Všimněte si, že je Cauchyova posloupnost. Intuitivně oddělit a , monoid by měl počítat alespoň do , tedy vyžaduje alespoň elementy. Od té doby je Cauchyova posloupnost, je skutečně profinitní slovo.
Dále slovo je idempotentní. To je způsobeno skutečností, že pro jakýkoli morfismus s N konečný, . Od té doby N je konečný, protože i dost skvělé, je idempotentní a posloupnost je konstantní.
Podobně, a jsou definovány jako a resp.
Neurčité jazyky
Pojem neurčitých jazyků umožňuje spojit pojmy teorie poloskupin k pojmům topologie. Přesněji řečeno P v neúplném jazyce, ekvivalentní jsou následující tvrzení:
- P je clopen.
- P je rozpoznatelné,
- The syntaktická kongruence z P je clopen, jako podmnožina .
Podobné výroky platí i pro jazyky P konečných slov. Následující podmínky jsou ekvivalentní.
- je rozpoznatelný (jako podmnožina ),
- the uzavření z P, , je rozpoznatelný (jako podmnožina ), kde
- , pro nějaké clopen K.,
- je clopen.
Tyto charakteristiky jsou způsobeny obecnější skutečností, že uzavření jazyka konečných slov a omezení jazyka neurčitého na konečná slova jsou inverzní operace, pokud se použijí na rozpoznatelné jazyky.
Reference
Pin, Jean-Éric (2016-11-30). Matematické základy teorie automatů (PDF). str. 130–139.Almeida, J (1994). Konečné poloskupiny a univerzální algebra. River Edge, NJ: World Scientific Publishing Co. Inc. ISBN 981-02-1895-8.