Řetězcové operace - String operations - Wikipedia

v počítačová věda, v oblasti teorie formálního jazyka, často se používá celá řada řetězcové funkce; použitá notace se však liší od použité programování a některé běžně používané funkce v teoretické sféře 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 ${ displaystyle varepsilon}$Zřetězení dvou řetězců ${ displaystyle s}$ a ${ displaystyle t}$ je označen ${ displaystyle s cdot t}$nebo kratší o ${ displaystyle st}$Zřetězení s prázdným řetězcem nedělá žádný rozdíl: ${ displaystyle s cdot varepsilon = s = varepsilon cdot s}$Zřetězení řetězců je asociativní: ${ 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}$.

A Jazyk je konečná nebo nekonečná sada řetězců. Kromě obvyklých operací množin, jako je sjednocení, křižovatka atd., lze na jazyky použít zřetězení: pokud oba ${ displaystyle S}$ a ${ displaystyle T}$ jsou jazyky, jejich zřetězení ${ displaystyle S cdot T}$ je definována jako sada zřetězení libovolného řetězce z ${ displaystyle S}$ a jakýkoli řetězec z ${ displaystyle T}$formálně ${ displaystyle S cdot T = {s cdot t mid s v S land t v T }}$Znovu tečka zřetězení ${ displaystyle cdot}$ je pro stručnost často vynechán.

Jazyk ${ displaystyle { varepsilon }}$ skládající se pouze z prázdného řetězce je třeba odlišit od prázdného jazyka ${ displaystyle {}}$Zřetězení jakéhokoli jazyka s prvním jazykem nedělá žádné změny: ${ displaystyle S cdot { varepsilon } = S = { varepsilon } cdot S}$, zatímco zřetězení s druhým vždy přináší prázdný jazyk: ${ displaystyle S cdot {} = {} = {} cdot S}$Zřetězení jazyků je asociativní: ${ displaystyle S cdot (T cdot U) = (S cdot T) cdot U}$.

Například zkratka ${ 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 }}$, sada všech třímístných desetinných čísel se získá jako ${ displaystyle D cdot D cdot D}$. Sada všech desetinných čísel libovolné délky je příkladem pro nekonečný jazyk.

Abeceda řetězce

The abeceda řetězce je sada všech znaků, které se vyskytují v konkrétním řetězci. Li s je řetězec, jeho abeceda je označen

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

The abeceda jazyka ${ displaystyle S}$ je sada všech znaků, které se vyskytují v libovolném řetězci ${ displaystyle S}$, formálně:${ displaystyle operatorname {Alph} (S) = bigcup _ {s in S} operatorname {Alph} (s)}$.

Například sada ${ displaystyle { langle a rangle, langle c rangle, langle o rangle }}$ je abeceda řetězce ${ displaystyle langle kakao rangle}$a výše ${ displaystyle D}$ je abeceda výše Jazyk ${ displaystyle D cdot D cdot D}$ stejně jako jazyk všech desetinných čísel.

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

Nechat L být Jazyk, a nechť Σ je jeho abeceda. A substituce řetězce nebo jednoduše a substituce je mapování F který mapuje znaky v Σ na jazyky (případně v jiné abecedě). Tak například daný znak A One Σ, 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 charakter A ∈ Σ. Substituce řetězců lze rozšířit na celé jazyky jako ^[1]

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

Běžné jazyky jsou uzavřeny pod substitucí řetězce. To znamená, že pokud je každý znak v abecedě běžného jazyka nahrazen jiným běžným jazykem, výsledkem bude stále běžný jazyk.^[2]Podobně, bezkontextové jazyky jsou uzavřeny pod substitucí řetězce.^{[3][poznámka 1]}

Jednoduchým příkladem je převod F_vidíš(.) na velká písmena, která mohou být definována např. jak následuje:

Pro rozšíření F_vidíš na struny, máme např.

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

Pro rozšíření F_vidíš do jazyků, máme např.

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

Řetězcový homomorfismus

A řetězový homomorfismus (často označované jednoduše jako a homomorfismus v teorie formálního jazyka ) je substituce řetězce, takže každý znak je nahrazen jedním řetězcem. To znamená ${ displaystyle f (a) = s}$, kde ${ displaystyle s}$ je řetězec pro každý znak ${ displaystyle a}$.^{[poznámka 2][4]}

Řetězcové homomorfismy jsou monoidní morfismy na volný monoid, zachování prázdného řetězce a binární operace z zřetězení řetězce. Vzhledem k tomu, jazyk ${ displaystyle L}$, sada ${ displaystyle f (L)}$ se nazývá homomorfní obraz z ${ displaystyle L}$. The inverzní homomorfní obraz řetězce ${ displaystyle s}$ je definován jako

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

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

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

Obecně, ${ displaystyle f (f ^ {- 1} (L)) neq L}$, zatímco jeden ano

${ 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.^[5] Podobně jsou bezkontextové jazyky uzavřeny pod homomorfismy^{[Poznámka 3]} a inverzní homomorfismy.^[6]

Řetězcový homomorfismus se říká, že je bez ε (nebo e-free), pokud ${ displaystyle f (a) neq varepsilon}$ pro všechny A v abecedě ${ displaystyle Sigma}$. Jednoduché jedno písmeno substituční šifry jsou příklady (bez ε) řetězcových homomorfismů.

Příklad homomorfismu řetězce G_vidíš lze také získat definicí podobnou jako výše substituce: G_vidíš(‹A›) = ‹A›, ..., G_vidíš(‹0›) = ε, ale necháme G_vidíš být nedefinováno na interpunkčních znacích. Příklady inverzních homomorfních obrazů jsou

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

U druhého jazyka G_vidíš(G_vidíš⁻¹({‹A›, ‹bb›})) = G_vidíš({‹A›}) = {‹A›} ≠ {‹A›, ‹bb›}. Homomorfismus G_vidíš není ε-free, protože mapuje např. ‹0› až ε.

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

Řetězcová projekce

Li s je řetězec a ${ displaystyle Sigma}$ je abeceda, řetězcová projekce z s je řetězec, jehož výsledkem je odstranění všech znaků, které nejsou v ${ displaystyle Sigma}$. Je psán jako ${ displaystyle pi _ { Sigma} (s) ,}$. Formálně je definován odstraněním znaků z pravé strany:

${ 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 {a}} a in Sigma end {případy}}}$

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

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

${ displaystyle pi _ { Sigma} (L) = { pi _ { Sigma} (s) vert s v L }}$^{[Citace je zapotřebí ]}

Správný kvocient

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

${ 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ě ${ displaystyle S podmnožina M}$ monoidu ${ displaystyle M}$, lze definovat podmnožinu kvocientu jako

${ 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.^{[Citace je zapotřebí ]}

Hopcroft a Ullman (1979) definují podíl L₁/L₂ jazyků L₁ a L₂ přes stejnou abecedu jako L₁/L₂ = { s | ∃t∈L₂. Svatý∈L₁ }.^[7]Nejedná se o zobecnění výše uvedené definice, protože pro řetězec s a odlišné znaky A, b, Hopcroftova a Ullmanova definice znamená {sa} / {b} dává {}, spíše než {ε}.

Levý kvocient (je-li definován podobně jako Hopcroft a Ullman 1979) singletonského jazyka L₁ a libovolný jazyk L₂ je známý jako Brzozowského derivát; -li L₂ je reprezentován a regulární výraz, tak může být i levý kvocient.^[8]

Syntaktický vztah

Správný kvocient podmnožiny ${ displaystyle S podmnožina M}$ monoidu ${ displaystyle M}$ definuje vztah ekvivalence, volal že jo syntaktický vztah z S. Je to dáno

${ 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, S je pak a běžný jazyk, tj. jazyk, který lze rozpoznat podle a konečný stavový automat. To je podrobněji popsáno v článku o syntaktické monoidy.^{[Citace je zapotřebí ]}

Správné zrušení

The správné zrušení postavy A z řetězce s je odstranění prvního výskytu postavy A v řetězci s, počínaje od pravé strany. Označuje se jako ${ displaystyle s div a}$ a je rekurzivně definována jako

${ 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 projekce dojíždět:

${ displaystyle pi _ { Sigma} (s) div a = pi _ { Sigma} (s div a)}$^{[Citace je zapotřebí ]}

Předpony

The předpony řetězce je množina všech předpony na řetězec, 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}$.

The předpona uzavření 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řena -li ${ displaystyle operatorname {pref} (L) = L}$.

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

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

The relace předpony je binární relace ${ displaystyle sqsubseteq}$ takhle ${ displaystyle s sqsubseteq t}$ kdyby a jen kdyby ${ displaystyle s in operatorname {Pref} _ {L} (t)}$. Tento vztah je konkrétním příkladem a pořadí prefixů.^{[Citace je zapotřebí ]}

Viz také

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

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.)