Operacje na łańcuchach

W informatyce , w obszarze teorii języka formalnego , często wykorzystuje się różne funkcje łańcuchowe ; jednak używana notacja różni się od tej używanej do programowania komputerów , a niektóre powszechnie używane funkcje w sferze teoretycznej są rzadko używane podczas programowania. W tym artykule zdefiniowano niektóre z tych podstawowych terminów.

Struny i języki

Łańcuch to skończony ciąg znaków. Pusty ciąg jest oznaczony przez ${\ displaystyle \ varepsilon}$ . Połączenie dwóch łańcuchów $i$ jest oznaczone przez ${\ Displaystyle s \ cdot t}$$lub$ krócej przez $displaystyle st}$ . Łączenie z pustym ciągiem nie ma znaczenia: ${\ Displaystyle s \ cdot \ varepsilon = s = \ varepsilon \ cdot s}$ . $\ cdot u$ \ cdot (t \ cdot u) = (s \ cdot t ) } .

Na przykład ${\ Displaystyle (\ langle b \ rangle \ cdot$ .

Język to skończony lub nieskończony zbiór ciągów znaków . Oprócz zwykłych operacji na zbiorach, takich jak suma, przecięcie itp., Konkatenację można zastosować do języków: jeśli zarówno $\ displaystyle S \ cdot T}$$jak$ i są językami, ich konkatenacja ${$$}$ zdefiniowany jako zbiór konkatenacji dowolnego ciągu z z , formalnie $displaystyle$${\ Displaystyle S \ cdot T = \ {s \ cdot t \ mid s \ w S \ ziemia t \ w T \}}$ . Ponownie, kropka konkatenacji $często$ pomijana dla zwięzłości.

Język składający $}}$${$ \ . Łączenie dowolnego języka z pierwszym nie powoduje żadnych zmian: ${\ Displaystyle S \ cdot \ {\ varepsilon \} = S = \ {\ varepsilon \} \ cdot S }$ , podczas gdy konkatenacja z tym ostatnim zawsze daje pusty język: ${\ Displaystyle S \ cdot \ {\} = \ {\} = \ {\} \ cdot S}$ . Łączenie języków jest asocjacyjne: ${\ Displaystyle S \ cdot (T \ cdot U) = (S \ cdot T) \ cdot U}$ .

Na przykład skrót ${\ 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 \}}$ , zbiór wszystkich trzycyfrowych liczb dziesiętnych otrzymuje się jako ${\ Displaystyle D \ cdot D \ cdot D}$ . Zbiór wszystkich liczb dziesiętnych o dowolnej długości jest przykładem języka nieskończonego.

Alfabet ciągu

Alfabet łańcucha to zbiór wszystkich znaków, które występują w określonym ciągu. Jeśli s jest ciągiem, jego alfabet jest oznaczony przez

${\ Displaystyle \ nazwa operatora {Alph} (s)}$

Alfabet języka to zbiór wszystkich znaków, które występują w dowolnym ciągu $,$$formalnie$$\$ Alph .

Na przykład zbiór ${\ Displaystyle \ {\ langle a \ rangle, \ langle c \ rangle, \ langle o \ rangle \}}$ to alfabet łańcucha $\ rangle}$$\ langle$ , a powyższy alfabetem powyższego języka ${\ Displaystyle D \ cdot D \ cdot D}$ , a także języka wszystkich liczb dziesiętnych.

Podstawianie ciągów

Niech L będzie językiem , a Σ jego alfabetem. Podstawienie łańcucha lub po prostu podstawienie to odwzorowanie f , które odwzorowuje znaki w Σ na języki (prawdopodobnie w innym alfabecie). Zatem, na przykład, mając znak a ∈ Σ, mamy f ( a )= L _a, gdzie L _a ⊆ Δ ^* jest językiem, którego alfabetem jest Δ. To odwzorowanie można rozszerzyć na ciągi jako

fa (ε)=ε

dla pustego łańcucha ε i

fa ( sa ) ​​= fa ( s ) fa ( za )

dla ciągu s ∈ L i znaku a ∈ Σ. Podstawienia ciągów można rozszerzyć na całe języki, jak

${\ Displaystyle f (L) = \ bigcup _ {s \ w L} f (s)}$

Języki regularne są zamknięte pod podstawieniem łańcucha. Oznacza to, że jeśli każdy znak w alfabecie języka regularnego zostanie zastąpiony innym językiem regularnym, wynikiem jest nadal język regularny. Podobnie języki bezkontekstowe są zamknięte pod podstawieniem łańcucha.

Prostym przykładem jest konwersja f _uc (.) na wielkie litery, którą można zdefiniować np. następująco:

postać	odwzorowane na język	uwaga
X	f uc ( x )
‹ a ›	{ ‹ A › }	odwzoruj znak małej litery na odpowiedni znak wielkiej litery
‹A › _ _	{ ‹ A › }	mapuj wielkie litery na siebie
‹ ß ›	{ ‹ SS › }	brak dostępnych znaków wielkich liter, zamapuj na łańcuch dwuznakowy
‹0›	{ε}	mapuj cyfrę na pusty ciąg
‹!›	{}	zakazać interpunkcji, mapować na pusty język
...		podobnie dla innych znaków

Dla rozszerzenia f _uc na łańcuchy mamy np

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

Dla rozszerzenia f _uc na języki mamy np

• f _uc ({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.

Homomorfizm strun

Homomorfizm ciągów (często określany po prostu jako homomorfizm w teorii języka formalnego ) to podstawienie ciągu znaków w taki sposób, że każdy znak jest zastępowany pojedynczym ciągiem. To znaczy $jest$ gdzie $ciąg$ znaków dla $a$ .

Homomorfizmy strunowe to morfizmy monoidalne na wolnej monoidzie , zachowujące pustą strunę i binarną operację konkatenacji strun . Biorąc $obrazem$$displaystyle$ język $L}$ zbiór nazywa się L { Odwrotny homomorficzny obraz $zdefiniowany$ jest jako

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

podczas gdy odwrotny homomorficzny obraz języka jest zdefiniowany jako ${\ displaystyle L}$

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

Ogólnie ${\ Displaystyle f (f ^ {- 1} (L)} \ neq L}$ , podczas gdy ma się

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

I

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

dla dowolnego języka ${\ displaystyle L}$ .

Klasa języków regularnych jest zamknięta na homomorfizmy i homomorfizmy odwrotne. Podobnie języki bezkontekstowe są zamknięte na homomorfizmy i homomorfizmy odwrotne.

Mówi się, że homomorfizm strun jest wolny od ε (lub wolny od e), $Sigma$ Σ { \ $}$ . Proste jednoliterowe szyfry podstawieniowe są przykładami (wolnych od ε) homomorfizmów łańcuchowych.

Przykładowy homomorfizm struny g _uc można również otrzymać definiując podobnie do powyższego podstawienia: g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, ale pozwalając g _uc być niezdefiniowanym na znakach interpunkcyjnych. Przykładami odwrotnych obrazów homomorficznych są

• g _uc ⁻¹ ({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, ponieważ g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS›, i
• g _uc ⁻¹ ({ ‹A›, ‹bb› }) = { ‹a› }, ponieważ g _uc (‹a›) = ‹A›, natomiast ‹bb› nie może być osiągnięte przez g _uc .

Dla tego ostatniego języka g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } . Homomorfizm g _uc nie jest wolny od ε, ponieważ odwzorowuje np. ‹0› na ε.

Bardzo prostym przykładem homomorfizmu napisów, który odwzorowuje każdy znak tylko na jeden znak, jest konwersja łańcucha zakodowanego w EBCDIC na ASCII .

Projekcja strun

Jeśli s jest ciągiem, a $alfabetem$ , projekcja ciągu s jest ciągiem powstałym w wyniku usunięcia wszystkich znaków, których nie ma w $\ Sigma}$ displaystyle . Jest napisane jako ${\ Displaystyle \ pi _ {\ Sigma} (s) \,}$ . Jest to formalnie zdefiniowane przez usunięcie znaków z prawej strony:

${\ Displaystyle \ pi _ {\ Sigma} (s) = {\ rozpocząć {przypadki} \ varepsilon & {\ mbox {jeśli}} s = \ varepsilon {\ mbox {pusty ciąg}} \\\ pi _ {\ Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s= ta{\mbox{ i }}a\w \Sigma \end{przypadki}}}$

Tutaj oznacza $znaków$ ciąg . Projekcja struny jest zasadniczo taka sama jak projekcja w algebrze relacyjnej .

Projekcja łańcuchowa może zostać podniesiona do projekcji języka . Biorąc pod uwagę język formalny L , jego projekcja jest dana przez

${\ Displaystyle \ pi _ {\ Sigma} (L) = \ {\ pi _ {\ Sigma} (s) \ \ vert \ s \ w L \}} [$

Właściwy iloraz

Prawy iloraz znaku a z łańcucha s jest obcięciem znaku a w łańcuchu s , z prawej strony. Jest oznaczony jako ${\ displaystyle s / a}$ . Jeśli łańcuch nie ma po prawej stronie, wynikiem jest pusty ciąg. Zatem:

${\ Displaystyle (sa) / b = {\ rozpocząć {przypadki} s & {\ mbox {jeśli}} a = b \\\ varepsilon & { \mbox{if }}a\neq b\end{przypadki}}}$

Iloraz pustego łańcucha można przyjąć:

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

Podobnie, biorąc pod uwagę podzbiór monoidu , można zdefiniować podzbiór ilorazu jako $\ subset M$$}$

${\ Displaystyle S / a = \ {s \ w M \ \ vert \ sa \ w S \}}$

Lewe ilorazy można zdefiniować podobnie, przy czym operacje odbywają się po lewej stronie łańcucha.

Hopcroft i Ullman (1979) definiują iloraz L ₁ / L ₂ języków L ₁ i L ₂ w tym samym alfabecie jako L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ }. Nie jest to uogólnienie powyższej definicji, ponieważ dla łańcucha s i różnych znaków a , b , definicja Hopcrofta i Ullmana implikuje { sa } / { b } plonowanie {} zamiast { ε }.

Lewy iloraz (zdefiniowany podobnie jak Hopcroft i Ullman 1979) języka singletonowego L ₁ i dowolnego języka L ₂ jest znany jako pochodna Brzozowskiego ; jeśli L ₂ jest reprezentowane przez wyrażenie regularne , więc może być lewym ilorazem.

Relacja składniowa

Właściwy iloraz $,$ definiuje relację $równoważności$ zwaną właściwą _ S . _ Podaje się przez

${\ Displaystyle \ sim _ {S} \; \, = \, \ {(s, t) \ w M \ razy M \ \ vert \ S / s = S / t \} }$

Relacja ma wyraźnie skończony indeks (ma skończoną liczbę klas równoważności) wtedy i tylko wtedy, gdy iloraz praw rodziny jest skończony; czyli jeśli

${\ Displaystyle \ {S / m \ \ vert \ m \ w M \}}$

jest skończony. W przypadku, gdy M jest monoidem słów nad jakimś alfabetem, S jest wtedy językiem regularnym , to znaczy językiem, który może być rozpoznany przez automat skończony . Zostało to omówione bardziej szczegółowo w artykule na temat monoidów składniowych .

Właściwe anulowanie

Prawidłowe anulowanie znaku a z łańcucha s to usunięcie pierwszego wystąpienia znaku a w łańcuchu s , zaczynając od prawej strony. Jest oznaczony jako i jest definiowany rekurencyjnie jako ${\ displaystyle s \ div a}$

$\ Displaystyle (sa) \ div b = {\ rozpocząć {przypadki} s & {\ mbox {jeśli}} a = b \\(s\div b)a&{\mbox{if }}a\neq b\end{przypadki}}}$

Pusty ciąg można zawsze anulować:

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

Oczywiście, prawe anulowanie i dojazd do projekcji :

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

Przedrostki

Prefiksy łańcucha to zbiór wszystkich przedrostków łańcucha, w odniesieniu do danego języka:

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

gdzie ${\ displaystyle s \ w L}$ .

Zamknięcie przedrostka języka to

${\ Displaystyle \ nazwa operatora {Pref} (L) = \ bigcup _ {s \ w L} \ nazwa operatora {Pref} _ {L} (s) = \ lewo \ {t \ \ vert \ s = tu; s \ w L;t,u\in \nazwa_operatora {Alph} (L)^{*}\right\}}$

Przykład: ${\ Displaystyle L = \ lewo \ {abc \ prawo \} {\ mbox {wtedy}} \ nazwa_operatora {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}$

Język nazywa się przedrostkiem zamkniętym , jeśli ${\ Displaystyle \ operatorname {Pref} (L) = L}$ .

Operator zamknięcia przedrostka jest idempotentny :

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

Relacja przedrostkowa jest relacją binarną taką, że $s \ sqsubseteq t}$$\ Displaystyle$${\ Displaystyle s \ in \ operatorname {Pref} _{L}(t)}$ wtedy i tylko wtedy, gdy . Ta relacja jest szczególnym przykładem kolejności przedrostków .

Zobacz też

• Porównanie języków programowania (funkcje łańcuchowe)
• Lemat Leviego
• String (informatyka) — definiowanie i realizacja bardziej podstawowych operacji na stringach

Notatki

•    Hopcroft, John E.; Ullman, Jeffrey D. (1979). Wprowadzenie do teorii automatów, języków i obliczeń . Reading, Massachusetts: Wydawnictwo Addison-Wesley. ISBN 978-0-201-02988-8 . Zbl 0426.68001 . (Patrz rozdział 3.)