Operacje String - String operations

W informatyce , w dziedzinie teorii języków formalnych , często korzysta się z różnych funkcji string ; Jednak notacja stosowana jest inna od tej stosowanej do programowania , a niektóre powszechnie używane funkcje w sferze teoretycznej są rzadko stosowane podczas programowania. Ten artykuł określa niektóre z tych podstawowych pojęć.

Struny i języki

Ciąg jest skończonym ciągiem znaków. Pusty ciąg oznaczamy przez . Konkatenacją dwa łańcucha i jest oznaczony lub krótszy . Złączenie z pustym ciągiem znaków nie ma znaczenia: . Konkatenacji ciągów jest łączne: . ${\ Displaystyle \ varepsilon}$${\ S} displaystyle$${\ T} displaystyle$${\ Displaystyle s \ t} cdot$${\ Displaystyle St}$${\ Displaystyle s \ cdot \ varepsilon = s = \ varepsilon \ cdot s}$${\ Displaystyle s \ cdot (t \ cdot U) = (S \ cdot t) \ cdot U}$

Na przykład . ${\ Displaystyle (\ langle b \ rangle \ cdot \ langle l \ rangle) \ cdot (\ varepsilon \ cdot \ langle ach \ rangle) = \ langle bl \ rangle \ cdot \ langle ach \ rangle = \ langle bla \ rangle}$

Język jest skończony lub nieskończony zbiór ciągów. Oprócz zwykłych zestaw operacji, takich jak unia, skrzyżowania itp konkatenacji może być stosowana do językach: jeśli oba i są językami, ich powiązanie jest zdefiniowany jako zbiór powiązań, o dowolny ciąg od i dowolny ciąg od formalnie . Ponownie, dot konkatenację często jest pominięty dla zachowania zwięzłości. ${\ S} displaystyle$${\ Displaystyle T}$${\ Displaystyle S \ cdot T}$${\ S} displaystyle$${\ Displaystyle T}$${\ Displaystyle S \ cdot T = \ {e \ cdot t \ MID s \ S \ w ziemi w t \ t \}}$${\ Displaystyle \ cdot}$

Język składający się tylko z pustym ciągiem należy odróżnić od pustego języku . Łącząc dowolny język z dawna nie czyni żadnej zmiany: , natomiast łączenie z nią zawsze daje pusty język: . Łączenie języków jest łączne: . ${\ 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}$

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

Alfabet sznurku

Alfabet ciąg jest zbiorem wszystkich znaków, które występują w danym ciągu znaków. Jeśli s jest ciągiem znaków, jego alfabet oznaczamy

${\ Displaystyle \ OperatorName {alf} (y)}$

Alfabet języka to zbiór wszystkich znaków, które występują w dowolny ciąg , formalnie: . ${\ S} displaystyle$${\ S} displaystyle$${\ Displaystyle \ OperatorName alf} {(S) = \ _ bigcup {s \ in S} \ OperatorName {alf} (y)}$

Na przykład, zestaw jest alfabet napisu , a powyżej jest alfabet z powyższym języku , jak również języka wszystkich liczb dziesiętnych. ${\ Displaystyle \ {\ langle A \ rangle \ langle c \ rangle \ langle O \ rangle \}}$${\ Displaystyle \ langle kakao \ rangle}$ ${\ Displaystyle D}$${\ Displaystyle d \ cdot D \ D} cdot$

substytucja String

Niech L będzie językiem , niech Σ być jego alfabet. Substytucji ciąg lub po prostu podstawienie jest odwzorowaniem f który odwzorowuje znaki Ď języków (ewentualnie w innym alfabecie). Tak więc, na przykład, biorąc pod uwagę charakter ∈ Σ, trzeba F ( ) = L _a, gdzie L ⊆ Δ ^* jest część języka, którego alfabet jest Δ. To odwzorowanie może zostać przedłużony do strun jak

F (ε) = ε

na pusty ciąg ε i

F ( SA ) = f ( a ) F ( )

STRING s ∈ L i charakteru ∈ Ď. Podstawienia łańcuch może zostać przedłużony do całych językach,

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

Języki regularne są zamknięte pod substytucji strun. Oznacza to, że jeśli każdy znak w alfabecie języka regularnego jest podstawiona przez inny język regularny, wynik jest jeszcze język regularny. Podobnie bezkontekstowych języki są zamknięte pod podstawienia łańcuchów.

Prostym przykładem jest konwersja F _UC duże litery, które mogą być określone na przykład w następujący sposób ().:

postać	odwzorowane na języku	uwaga
x	f UC ( x )
< >	{< >}	map małą char do odpowiednich wielką char
< >	{< >}	map wielką char do siebie
< SS >	{< SS >}	nie wielkie char dostępnych map do dwóch char ciąg
<0>	{Ε}	mapa cyfra pusty ciąg
<!>	{}	zabronić interpunkcyjnych, mapę do pustej języku
...		Podobny do innych znaków

Dla przedłużenia f _uc do strun, mamy np

• f _UC (<Str>) = {<S>} ⋅ {<t>} ⋅ {<R>} ⋅ {A-} ⋅ {<SS>} ⋅ {<e>} = {<STRASSE>},
• f _UC (<U2>) = {<U>} ⋅ {ε} = {<U>} i
• f _UC (<wartych>) = {<G>} ⋅ {<o>} ⋅ {} = {}.

Dla przedłużenia f _uc do języków, mamy np

• f _UC ({<Str> <U2> <wartych>}) = {<STRASSE>} ∪ {<U>} ∪ {} = {<STRASSE> <U>}.

homomorfizm String

Homomorfizm ciąg (często określane po prostu jako homomorfizmu w teorii języków formalnych ) jest substytucja ciąg taki, że każdy znak jest zastąpione jednym ciągiem. Oznacza to, że , gdzie jest ciągiem znaków, dla każdego znaku .${\ Displaystyle Rf (A) = y}$${\ S} displaystyle$${\ A} displaystyle$

Homomorfizmy String są monoid morfizmami na wolnym monoid , zachowując pusty ciąg i binarne operację z łańcuchów znaków . Biorąc pod uwagę język , zestaw nazywa się homomorphic obraz z . Odwrotny homomorphic obraz z ciąg jest zdefiniowany jako ${\ L} displaystyle$${\ Displaystyle F (L)}$${\ L} displaystyle$${\ S} displaystyle$

${\ Displaystyle f ^ {- 1} (s) = \ {W | F (z) = S \}}$

natomiast odwrotna homomorphic obraz języka jest zdefiniowana jako ${\ L} displaystyle$

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

Na ogół , gdy jeden ma ${\ Displaystyle F (f ^ {- 1} (l)) \ L} Neq$

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

i

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

na dowolny język . ${\ L} displaystyle$

Klasa języków regularnych jest zamknięta pod homomorfizmów i odwrotnych homomorfizmów. Podobnie języków bezkontekstowych są zamknięte pod homomorfizmów i odwrotnych homomorfizmów.

Homomorfizmem ciąg mówi się ε-free (lub e-free), jeśli dla wszystkich w alfabecie . Proste pojedynczej nas szyfry podstawienia są przykładami (e-free) homomorfizmów smyczkowych. ${\ Displaystyle f (a) \ neq \ varepsilon}$${\ Displaystyle \ Sigma}$

Przykład ciąg homomorfizm g _UC można również uzyskać przez określenie podobny do powyżej podstawień: G _UC (<a>) = a, ..., g _UC (<0>) = ε, lecz pozwalając g _UC niezdefiniowane znaków interpunkcyjnych na. Przykłady obrazów są odwrotne homomorphic

• g _UC ^-1 ({<SSS>}) = {<SSS> <SSS> <SSS>}, ponieważ g _UC (<SSS>) = g _UC (<SSS>) = g _UC (<SSS>) = <SSS> i
• g _UC ^-1 ({a, <bb>}) = {Ra} ponieważ g _UC (Ra) = a, natomiast <bb> nie można uzyskać poprzez g _uc .

Na drugim języku g _UC ( g _UC ^-1 ({a, <bb>})) = g _UC ({Ra}) = {A-} ≠ {a, <bb>} , Homomorfizm g _UC nie jest ε-wolny, ponieważ odwzorowuje to np <0>, aby ε.

Bardzo prosty przykład ciąg homomorfizm że odwzorowuje każdy znak tylko charakter jest konwersja EBCDIC kodowanego ciągu do ASCII .

projekcja String

Jeśli s jest ciągiem znaków, i jest alfabetu, projekcja ciąg od s jest ciąg znaków, który powoduje, usuwając wszystkie znaki, które nie są . Jest napisane jak . To jest formalnie zdefiniowany przez usunięcie znaków z prawej strony: ${\ Displaystyle \ Sigma}$${\ Displaystyle \ Sigma}$${\ Displaystyle \ pi _ {\ Sigma} (e) \}$

${\ Displaystyle \ pi _ {\ Sigma} (s) = {\ {zaczynać przypadków} \ varepsilon & {\ mbox {if}}, s = \ varepsilon {\ mbox {pusty ciąg}} \\\ pi _ {\ sigma} (t) i {\ mbox {if}}, s = TA {\ mbox {i}} a \ Notin \ \\\ sigma pi _ {\ sigma} (t), i {\ mbox {if}}, s = TA {\ mbox {i}} a \ w \ Sigma \ koniec {przypadków}}}$

Tutaj oznacza ciąg pusty . Projekcja łańcucha jest w zasadzie taka sama, jak występ w relacyjnej Algebra . ${\ Displaystyle \ varepsilon}$

Projekcja ciąg może być promowany do projekcji języka . Biorąc pod uwagę język formalny L , jego występ jest dana przez

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

prawo iloraz

Prawy iloraz charakter A z ciągiem s jest obcięcie znaku A w łańcuchu s , z prawej strony. Jest on oznaczony jako . Jeżeli łańcuch nie posiada na prawej stronie, wynikiem jest pusty łańcuch. A zatem: ${\ Displaystyle s / a}$

${\ Displaystyle (SA) / B = {\ {zaczynać przypadków} i {s \ mbox {if}}: a = b \\\ varepsilon & {\ mbox {if}} a \ neq b \ koniec {przypadków}}}$

Iloraz ciągu pustego można podjąć:

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

Podobnie, ponieważ podzestaw z monoid , można określić jako iloraz podzbiór ${\ Displaystyle S \ K} podzbiór$${\} M displaystyle$

${\ Displaystyle S / A = \ {e \ wm \ \ vert \ sa \ in S \}}$

Left ilorazy mogą być definiowane podobnie, ze operacje odbywają się po lewej stronie napisu.

Hopcroft i Ullmana (1979) określa iloraz l ₁ / L ₂ języków L ₁ i L ₂ w tym samym alfabet jak l ₁ / L ₂ = { y | ∃ t ∈ L ₂ . st ∈ L ₁ }. Nie jest to uogólnienie powyższej definicji, gdyż na łańcuch a i różne postacie , b , definicja Hopcroft 'a Ullman implikuje { sa } / { b } uginając {}, zamiast {ε}.

W lewej iloraz (gdy zdefiniowane podobnie do Hopcroft i Ullmana 1979) języka pojedyncza L ₁ i dowolnym języku L ₂ jest znany jako Brzozowski pochodnej ; Jeśli L ₂ jest reprezentowany przez wyrażenie regularne , dzięki czemu mogą być lewy iloraz.

składniowym relacja

Prawo iloraz podzbioru z monoid określa stosunek równoważności , zwany prawo składniowym związek o S . Jest podawany przez ${\ Displaystyle S \ K} podzbiór$${\} M displaystyle$

${\ Displaystyle \ SIM _ {s} \; \, = \ \ {(s, t) \ wm \ m razy \ \ vert \ S / S = S / T \}}$

Relacja jest jasno indeksu skończonych (ma skończoną liczbę klas równoważności) wtedy i tylko wtedy, gdy rodzina prawy ilorazy jest skończony; to znaczy, jeśli

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

jest skończona. W przypadku, gdy M jest monoid słów nad pewnym alfabetem, S jest wtedy język regularny , to jest język, który może zostać uznany przez automat skończony państwowej . Jest to omówione bardziej szczegółowo w artykule o składniowych monoids .

prawo anulowania

Prawo anulowania charakter A z ciągiem s jest usunięcie pierwszego wystąpienia znaku A w łańcuchu s , zaczynając od prawej strony. Jest on oznaczony jako jest rekursywnie zdefiniowany jako ${\ Displaystyle s \ a} Div$

${\ Displaystyle (SA) \ dz B = {\ rozpocząć {przypadków} a i {\ mbox {if}}: a = b \\ (s \ dz B) i {\ mbox {if}} końcówkę \ neq b \ { przypadki}}}$

Pusty ciąg jest zawsze odwoływalny:

${\ Displaystyle \ varepsilon \ strefa A = \ varepsilon}$

Oczywiście, tak anulowanie i występ dojazdy :

${\ Displaystyle \ pi _ {\ Sigma} (e) \ strefa A = \ pi _ {\ Sigma} (s \ Div a)}$

prefiksy

Te prefiksy ciąg jest zbiorem wszystkich prefiksów do łańcucha, w odniesieniu do danego języka:

${\ Displaystyle \ OperatorName {Pref} _ {l} (s) = \ {t \ \ vert \ s = tu {\ mbox {do}} t, U \ w \ OperatorName {alf} (l) ^ {*} \}}$

gdzie . ${\ Displaystyle s \: L}$

Zamknięcie przedrostek języka jest

${\ Displaystyle \ OperatorName {Pref} (l) = \ bigcup _ {s \: L} \ OperatorName {Pref} _ {l} (s) = \ left \ {t \ \ vert \ s = TU; s \ w l t, U \ w \ OperatorName {alf} (l) ^ {*} \ prawo \}}$

Przykład:
${\ Displaystyle L = \ left \ {ABC \ prawo \} {\ mbox {następnie}} \ OperatorName {Pref} (l) = \ left \ {\ varepsilon A, AB, ABC \ prawo \}}$

Język nazywa prefiks zamknięte jeśli . ${\ Displaystyle \ OperatorName {Pref} (l) = l}$

Operator zamknięcie prefiks idempotent :

${\ Displaystyle \ OperatorName Pref} {(\ OperatorName {Pref} (l)) = \ OperatorName Pref} {(L)}$

Relacja prefiks jest binarna relacja taka, że wtedy i tylko wtedy . Zależność ta jest szczególnym przykładem celu prefiksu .${\ Displaystyle \ sqsubseteq}$${\ Displaystyle s \ t} sqsubseteq$${\ Displaystyle s \ w \ OperatorName {Pref} _ {l} (t)}$

Zobacz też

• Porównanie języków programowania (funkcje String)
• Leviego lemat
• String (informatyka) - definicja i realizacja kilku podstawowych operacji na strunach

Uwagi

Referencje

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