Řetězcové operace - String operations

V informatice se v oblasti teorie formálních jazyků často používá řada řetězcových funkcí ; použitý zápis se však liší od zápisu používaného pro počítačové programování a některé běžně používané funkce v teoretické oblasti se při programování používají jen zřídka. Tento článek definuje některé z těchto základních pojmů.

Řetězce a jazyky

Řetězec je konečná posloupnost znaků. Prázdný řetězec je označen . Zřetězení dvou řetězců a je označeno nebo kratší . Zřetězení s prázdným řetězcem nehraje žádnou roli: . Zřetězení řetězců je asociativní: . ${\ displaystyle \ varepsilon}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s \ cdot t}$${\ displaystyle st}$${\ displaystyle s \ cdot \ varepsilon = s = \ varepsilon \ cdot s}$${\ displaystyle s \ cdot (t \ cdot u) = (s \ cdot t) \ cdot u}$

Například . ${\ displaystyle (\ langle b \ rangle \ cdot \ langle l \ rangle) \ cdot (\ varepsilon \ cdot \ langle ah \ rangle) = \ langle bl \ rangle \ cdot \ langle ah \ rangle = \ langle blah \ rangle}$

Jazyk je konečný nebo nekonečný soubor řetězců. Kromě obvyklých operací se sadami, jako je sjednocení, křižovatka atd., Lze zřetězení použít na jazyky: pokud jsou oba a jsou jazyky, jejich zřetězení je definováno jako sada zřetězení libovolného řetězce od a libovolného řetězce od , formálně . Znovu je tečka zřetězení kvůli stručnosti často vynechána. ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cdot T}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cdot T = \ {s \ cdot t \ mid s \ v S \ land t \ v T \}}$${\ displaystyle \ cdot}$

Jazyk skládající se pouze z prázdného řetězce je třeba odlišit od prázdného jazyka . Zřetězení libovolný jazyk s bývalý nedělá žádné změny: při zřetězení s ním vždy dává prázdnou jazyk: . Zřetězení jazyků je asociativní: . ${\ displaystyle \ {\ varepsilon \}}$${\ displaystyle \ {\}}$${\ displaystyle S \ cdot \ {\ varepsilon \} = S = \ {\ varepsilon \} \ cdot S}$${\ displaystyle S \ cdot \ {\} = \ {\} = \ {\} \ cdot S}$${\ displaystyle S \ cdot (T \ cdot U) = (S \ cdot T) \ cdot U}$

Například zkratkou se sada všech třímístných desetinných čísel získá jako . Sada všech desetinných čísel libovolné délky je příkladem pro nekonečný jazyk. ${\ displaystyle D = \ {\ langle 0 \ rangle, \ langle 1 \ rangle, \ langle 2 \ rangle, \ langle 3 \ rangle, \ langle 4 \ rangle, \ langle 5 \ rangle, \ langle 6 \ rangle, \ langle 7 \ rangle, \ langle 8 \ rangle, \ langle 9 \ rangle \}}$${\ displaystyle D \ cdot D \ cdot D}$

Abeceda řetězce

Abeceda řetězce je množina všech znaků, které se vyskytují v určitém řetězci. Pokud s je řetězec, jeho abeceda je označena

${\ displaystyle \ operatorname {Alph} (s)}$

Abeceda jazyka je množina všech znaků, které se vyskytují v každém řetězci , formálně: . ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle \ operatorname {Alph} (S) = \ bigcup _ {s \ in S} \ operatorname {Alph} (s)}$

Sada je například abeceda řetězce a výše uvedená je abeceda výše uvedeného jazyka i jazyka všech desetinných čísel. ${\ displaystyle \ {\ langle a \ rangle, \ langle c \ rangle, \ langle o \ rangle \}}$${\ displaystyle \ langle kakao \ rangle}$ ${\ displaystyle D}$${\ displaystyle D \ cdot D \ cdot D}$

Střídání řetězců

Nechť L je jazyk a nechť Σ je jeho abeceda. Substituce řetězce nebo jednoduše substituce je mapování f, které mapuje znaky v Σ na jazyky (případně v jiné abecedě). Tak například, daný znak a ∈ Σ, jeden má f ( a ) = L _a kde L _a ⊆ Δ ^* je nějaký jazyk, jehož abeceda je Δ. Toto mapování lze rozšířit na řetězce jako

f (ε) = ε

pro prázdný řetězec ε a

f ( sa ) = f ( s ) f ( a )

pro řetězec s ∈ L a znak a ∈ Σ. Substituce řetězců lze rozšířit na celé jazyky jako

${\ displaystyle f (L) = \ bigcup _ {s \ v L} f (s)}$

Běžné jazyky jsou uzavřeny nahrazením řetězců. To znamená, že pokud je každý znak v abecedě běžného jazyka nahrazen jiným běžným jazykem, výsledkem je stále běžný jazyk. Podobně jsou bezkontextové jazyky uzavřeny substitucí řetězců.

Jednoduchým příkladem je převod f _uc (.) Na velká písmena, který lze definovat např. Takto:

charakter	namapováno na jazyk	Poznámka
X	f uc ( x )
< >	{< >}	mapovat malá písmena na odpovídající velká písmena
< >	{< >}	namapujte velká písmena na sebe
‹ Ss ›	{‹ SS ›}	není k dispozici velká písmena, namapujte na řetězec se dvěma znaky
‹0›	{ε}	namapujte číslici na prázdný řetězec
‹!›	{}	zakázat interpunkci, namapovat na prázdný jazyk
...		podobné pro ostatní znaky

Pro rozšíření f _uc na řetězce máme např

• f _uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›} a
• f _uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Pro rozšíření f _uc do jazyků, máme např

• f _uc ({‹Straße›, ‹u2›, ‹Přejít!›}) = {‹STRASSE›} ∪ {‹U›} ∪ {} = {‹STRASSE›, ‹U›}.

Řetězcový homomorfismus

String homomorphism (často odkazoval se na jednoduše jako homomorfismu v teorii formálních jazyků ) je řetězec substituce taková, že každý znak je nahrazena jediným řetězcem. To znamená, kde je řetězec pro každý znak .${\ displaystyle f (a) = s}$${\ displaystyle s}$${\ displaystyle a}$

String homomorphisms jsou monoidu morphisms na volné monoid , konzervační prázdný řetězec a binární operaci na zřetězením řetězce . Vzhledem k tomu, jazyk , soubor se nazývá homomorfní obraz o . Inverzní homomorfní obraz z řetězce je definován jako ${\ displaystyle L}$${\ displaystyle f (L)}$${\ displaystyle L}$${\ displaystyle s}$

${\ displaystyle f ^ {- 1} (s) = \ {w | f (w) = s \}}$

zatímco inverzní homomorfní obraz jazyka je definován jako ${\ displaystyle L}$

${\ displaystyle f ^ {- 1} (L) = \ {s | f (s) \ v L \}}$

Obecně platí, že zatímco člověk má ${\ displaystyle f (f ^ {- 1} (L)) \ neq L}$

${\ displaystyle f (f ^ {- 1} (L)) \ subseteq L}$

a

${\ displaystyle L \ subseteq f ^ {- 1} (f (L))}$

pro jakýkoli jazyk . ${\ displaystyle L}$

Třída regulárních jazyků je uzavřena pod homomorfismy a inverzními homomorfismy. Podobně jsou bezkontextové jazyky uzavřeny pod homomorfismy a inverzními homomorfismy.

Řetězec homomorphism je řekl, aby byl ε-volný (nebo e-volný) jestliže pro všechny a v abecedě . Jednoduché jednopísmenné substituční šifry jsou příklady řetězcových homomorfismů (bez ε). ${\ displaystyle f (a) \ neq \ varepsilon}$${\ displaystyle \ Sigma}$

Příklad homomorfismu řetězce g _uc lze také získat definováním podobné výše uvedené substituci: g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, ale necháme g _uc být nedefinováno na interpunkční znaky. Příklady inverzních homomorfních obrazů jsou

• g _uc ⁻¹ ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›}, protože g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS› a
• g _uc ⁻¹ ({‹A›, ‹bb›}) = {‹a›}, protože g _uc (‹a›) = ‹A›, zatímco ‹bb› nelze dosáhnout pomocí g _uc .

Pro tento druhý jazyk platí g _uc ( g _uc ⁻¹ ({‹A›, ‹bb›})) = g _uc ({‹a›}) = {‹A›} ≠ {‹A›, ‹bb›} . Homomorfismus g _uc není ε-free, protože mapuje např. ‹0› na ε.

Velmi jednoduchým příkladem řetězcového homomorfismu, který mapuje každý znak pouze na znak, je převod řetězce kódovaného EBCDIC na ASCII .

Řetězcová projekce

Pokud to je řetězec, a je abeceda je řetězec projekce ze sa je řetězec, který výsledky tím, že odstraní všechny znaky, které nejsou v . Je psán jako . Formálně je definován odstraněním znaků z pravé strany: ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ pi _ {\ Sigma} (s) \,}$

${\ displaystyle \ pi _ {\ Sigma} (s) = {\ begin {cases} \ varepsilon & {\ mbox {if}} s = \ varepsilon {\ mbox {prázdný řetězec}} \\\ pi _ {\ Sigma} (t) & {\ mbox {if}} s = ta {\ mbox {and}} a \ notin \ Sigma \\\ pi _ {\ Sigma} (t) a & \ \ mbox {if}} s = ta {\ mbox {and}} a \ in \ Sigma \ end {případy}}}$

Zde označuje prázdný řetězec . Projekce řetězce je v podstatě stejná jako projekce v relační algebře . ${\ displaystyle \ varepsilon}$

Řetězcová projekce může být povýšena na projekci jazyka . Vzhledem k formálnímu jazyku L je jeho projekce dána vztahem

${\ displaystyle \ pi _ {\ Sigma} (L) = \ {\ pi _ {\ Sigma} (s) \ \ vert \ s \ v L \}}$

Správný kvocient

Právo kvocient ze znaku A z řetězce s je zkrácení znakové A v řetězci s , z pravé strany. Označuje se jako . Pokud řetězec nemá na pravé straně znak a , výsledkem je prázdný řetězec. Tím pádem: ${\ displaystyle s / a}$

${\ displaystyle (sa) / b = {\ begin {cases} s & {\ mbox {if}} a = b \\\ varepsilon & {\ mbox {if}} a \ neq b \ end {cases}}}$

Kvocient prázdného řetězce lze vzít:

${\ displaystyle \ varepsilon / a = \ varepsilon}$

Podobně, vzhledem k podmnožině monoidů , lze definovat podmnožinu podmnožin jako ${\ displaystyle S \ podmnožina M}$${\ displaystyle M}$

${\ displaystyle S / a = \ {s \ v M \ \ vert \ sa \ v S \}}$

Levé kvocienty lze definovat podobně, přičemž operace probíhají nalevo od řetězce.

Hopcroft a Ullman (1979) definují kvocient L ₁ / L ₂ jazyků L ₁ a L ₂ ve stejné abecedě jako L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ }. Nejedná se o zobecnění výše uvedené definice, protože pro řetězec s a odlišné znaky a , b znamená Hopcroftova a Ullmanova definice { sa } / { b } poddajnost {}, spíše než {ε}.

Levý kvocient (definovaný podobně jako Hopcroft a Ullman 1979) singletonského jazyka L ₁ a libovolného jazyka L ₂ je známý jako Brzozowského derivát ; pokud L ₂ je reprezentován regulárním výrazem , může to být i levý kvocient.

Syntaktický vztah

Právo kvocient podmnožiny z monoid definuje vztah rovnocennosti , nazvaný právo syntaktický vztah ze S . Je to dáno ${\ displaystyle S \ podmnožina M}$${\ displaystyle M}$

${\ displaystyle \ sim _ {S} \; \, = \, \ {(s, t) \ v M \ krát M \ \ vert \ S / s = S / t \}}$

Tento vztah má jednoznačně konečný index (má konečný počet tříd ekvivalence) právě tehdy, pokud jsou kvocienty rodinných práv konečné; to je, pokud

${\ displaystyle \ {S / m \ \ vert \ m \ v M \}}$

je konečný. V případě, že M je monoid slov nad nějakou abecedou, je S potom běžný jazyk , tj. Jazyk, který lze rozpoznat automatem konečného stavu . To je podrobněji popsáno v článku o syntaktických monoidech .

Správné zrušení

Právo zrušení ze znaku A z řetězce s je odstranění prvního výskytu znaku A v řetězci s , počínaje od pravé straně. Je označen jako a je rekurzivně definován jako ${\ displaystyle s \ div a}$

${\ displaystyle (sa) \ div b = {\ begin {cases} s & {\ mbox {if}} a = b \\ (s \ div b) a & {\ mbox {if}} a \ neq b \ end { případy}}}$

Prázdný řetězec je vždy zrušitelný:

${\ displaystyle \ varepsilon \ div a = \ varepsilon}$

Je zřejmé, že správné zrušení a promítání dojíždí :

${\ displaystyle \ pi _ {\ Sigma} (s) \ div a = \ pi _ {\ Sigma} (s \ div a)}$

Předpony

Tyto předpony řetězec je množina všech prefixů na provázku, s ohledem na daný jazyk:

${\ displaystyle \ operatorname {Pref} _ {L} (s) = \ {t \ \ vert \ s = tu {\ mbox {for}} t, u \ in \ operatorname {Alph} (L) ^ {*} \}}$

kde . ${\ displaystyle s \ v L}$

Uzavření prefix jazyka je

${\ displaystyle \ operatorname {Pref} (L) = \ bigcup _ {s \ in L} \ operatorname {Pref} _ {L} (s) = \ left \ {t \ \ vert \ s = tu; s \ in L; t, u \ in \ operatorname {Alph} (L) ^ {*} \ right \}}$

Příklad:
${\ displaystyle L = \ left \ {abc \ right \} {\ mbox {then}} \ operatorname {Pref} (L) = \ left \ {\ varepsilon, a, ab, abc \ right \}}$

Jazyk se nazývá předpona uzavřená, pokud . ${\ displaystyle \ operatorname {pref} (L) = L}$

Operátor uzavření předpony je idempotentní :

${\ displaystyle \ operatorname {Pref} (\ operatorname {Pref} (L)) = \ operatorname {Pref} (L)}$

Vztah prefix je binární relace tak, že tehdy a jen tehdy, jestliže . Tato relace je konkrétním příkladem pořadí předpon .${\ displaystyle \ sqsubseteq}$${\ displaystyle s \ sqsubseteq t}$${\ displaystyle s \ in \ operatorname {Pref} _ {L} (t)}$

Viz také

• Porovnání programovacích jazyků (řetězcové funkce)
• Leviho lema
• Řetězec (informatika) - definice a implementace základních operací na řetězcích

Poznámky

Reference

• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu . Reading, Massachusetts: Addison-Wesley Publishing. ISBN  978-0-201-02988-8 . Zbl  0426.68001 . (Viz kapitola 3.)