문자열 연산

컴퓨터 과학에서, 형식 언어 이론의 영역에서는, 자주 사용하는 것은 다양한 문자열 함수로 만들어진다. 그러나, 사용하는 표기법은 컴퓨터 프로그래밍에 사용되는 것과 다르며, 이론 영역에서 일반적으로 사용되는 몇몇 기능들은 프로그래밍할 때 거의 사용되지 않는다.이 글은 이러한 기본적인 용어 중 일부를 정의하고 있다.

문자열 및 언어

문자열은 문자의 유한한 배열이다.The empty string is denoted by ${\displaystyle \varepsilon }$. The concatenation of two string ${\displaystyle s}$ and ${\displaystyle t}$ is denoted by ${\displaystyle s\cdot t}$, or shorter by ${\displaystyle st}$. Concatenating with the empty string makes no difference: ${\dis$$playstyle s\cdot \varepsilon =s=\varepsilon \cdot s$ 문자열의 연결은 $s{\displaystyle \cdot (tu}$)${\displaystyle }$= (${\displaystyle s}$t ) = ($s$t t )${\displaystyle }$u ${\displaystyle u}${\$displaysty$s\$cdot u=(s\cdot$t)\$cdot u$

For example, ${\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }$.

언어는 유한하거나 무한한 문자열의 집합이다.조합, 교차로 등과 같은 일반적인 세트 작업 외에도, $연결$은 언어에 적용될 수 있다: S ${\displaystyle$ S$}$ 및 $T$ ${\displaystyle T}$이(가) 언어인$$ 경우, 이들의 연결 $S{\displaystyle }$⋅ ${\displaystyle T}$ ${\displaystyle S\cdot T}$은 S ${\displaystystyle S}$ 및$$ 모든 스트린의 문자열 집합으로 정의된다$$.g from ${\displaystyle T}$, formally ${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$. Again, the concatenation dot ${\displaystyle \cdot }$ is often omitted for brevity.

빈 ${\displaystyle \mathrm{문자열}}$로만 구성된$$ {$\}$ {\$displaystyle \{\varepsilon \}$은(는) 빈 언어${\displaystyle \{\}}$ ${\displaystyle \{\}}$과(와) 구분되어야 한다$.$ 어떤 언어도 전자 언어와 연결해도 아무런 변화가 없다.${\displaystyle S}$ ${\displaystyle \cdot }$ {${\displaystyle \epsilon }$ ${\displaystyle \}}$= ${\displaystyle S}$= {${\displaystyle \epsilon }$ ${\displaystyle \}S}$ ${\displaystyle$ S$\cdot \{\varepsilon \}=S=\\\varepsilon \}\cdot S$ 후자와 연결하면 항상 빈 언어가 나온다.${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$. Concatenation of languages is associative: ${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$.

For example, abbreviating ${\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 \}}$, the set of all three-digit십진수는 $D{\displaystyle }$ ${\displaystyle \cdot }$ ${\displaystyle D}$ ${\displaystyle$ D$\cdot D\cdot$ D$}$로 $구한다$ 임의길이의 모든 십진수 세트는 무한언어의 예다.

문자열의 알파벳

문자열의 알파벳은 특정 문자열에서 발생하는 모든 문자의 집합이다.s가 문자열인 경우 문자열이 다음으로 표시됨

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

언어 $S{\displaystyle }$ ${\displaystyle S}$의 알파벳은 $S{\displaystyle }$ ${\displaystyle S}$의 문자열에서 발생하는 모든 문자의 집합이며$,$ 형식적으로는 다음과 같다.${\displaystyle \mathrm{Alph})}$ (${\displaystyle }$S ) = ${\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{s}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{S}}$ ${\displaystyle \mathrm{Alph}}$ ${\displaystyle }$( s${\displaystyle }$) ${\displaystyle \operatorname {Alph}(S)=\빅컵 _{s\in S}\operatorname {Alph}$ (s$)\}$ .

For example, the set ${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$ is the alphabet of the string ${\displaystyle \langle cacao\rangle }$, and the above ${\displaystyle D}$ is the alphabet of the above language ${\displaystyle D\cdot D\cdot D}$모든 소수점 이하 언어.

문자열 대체

L을 언어가 되게 하고, Ⅱ를 그 알파벳이 되게 하라.문자열 대체 또는 단순 대체는 σ의 문자를 언어(아마도 다른 알파벳)에 매핑하는 매핑 f이다.따라서 예를 들어, 문자 given σ이 주어지면 f(a)=L이_a 있는데 여기서_a L ⊆ Δ는^* 알파벳 Δ인 어떤 언어다.이 매핑은 다음과 같이 문자열로 확장될 수 있다.

f.

빈 문자열의 경우

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

문자열 s ∈ L 및 문자 ∈ σ. 문자열 대체는 다음과 같이 전체 언어로 확장될 수 있다.

${\displaystyle f(L)=\빅컵 _{s\in L}f}$

일반 언어는 문자열 대체에 의해 폐쇄된다.즉, 정규 언어의 알파벳에 있는 각 문자가 다른 정규 언어로 대체된다면 그 결과는 여전히 정규 언어인 것이다.^[2]마찬가지로, 문맥 없는 언어는 문자열 대체에서 닫힌다.^{[3][note 1]}

간단한 예로 대문자로의 변환_uc f(.)를 들 수 있는데, 다음과 같이 정의할 수 있다.

캐릭터	언어에 매핑된	평론하다
x	fuc(x)
‹›	{ ‹A› }	소문자를 해당 대문자에 매핑하십시오.
‹A›	{ ‹A› }	대문자를 그 자체에 매핑하다.
‹ß›	{ ‹SS› }	사용할 수 있는 대문자 없음, 2-char 문자열에 매핑
‹0›	{ ε }	숫자를 빈 문자열에 매핑
‹!›	{ }	구두점을 금지하다. 빈말로 지도하다.
...		다른 차자와 비슷한.

f를_uc 현으로 확장하기 위해, 예를 들어,

• f_uc(‹Straze›) = {‹S›} {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹TRASS›}}.
• f_uc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, 그리고
• f_uc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

언어에 대한 f의_uc 확장에 대해서는, 예를 들어,

• f_uc({ ‹Straze›, ‹u2›, ‹Go!› }) = { ‹TRASS› } { ‹U› } = { ‹TRASS, ‹U› } = { ‹TRASS› }.

끈 동형성

끈 동형성(string homomorphism, 종종 형식 언어 이론에서는 동형성이라고 일컬어짐)은 각 문자가 하나의 문자열로 대체되는 문자열이다.즉, ${\displaystyle f}$(${\displaystyle }$)${\displaystyle }$= s ${\displaystyle f(a)=s$ $여기$서 s ${\displaystyle s}$은 각 $문자{\displaystyle }$ a ${\displaystyle a}$에 대해 문자열이다$.$^{[note 2][4]}

문자열 동형성은 자유단모형의 단모형 형태로서, 빈 문자열과 문자열 결합의 이항연산을 보존한다.언어 $L{\displaystyle }$ ${\displaystyle L}$을$($를) 지정하면 $set{\displaystyle }$ f${\displaystyle }$(${\displaystyle L}$) ${\displaystyle f(L)}$을(를) $L{\displaystyle }$ ${\displaystyle L}$의 동형상이라고 한다$$$.$ 문자열 $s{\displaystyle }$ ${\displaysty s}$의 역동형상(역)은 다음과 같이 정의된다$$.

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

언어 $L{\displaystyle }$ ${\displaystyle L}$의 역동형 이미지는 다음과 같이 정의된다$$.

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

$일반적$으로 $f{\displaystyle (}$ ${\displaystyle f{}^{}}$- 1${\displaystyle {}^{}}$( L${\displaystyle }$)${\displaystyle \ne }$ ${\displaystyle L}$ ${\displaystyle f(f^{-1}(L))\neq$ L$\},$

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

그리고

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

$모든{\displaystyle }$ 언어 L ${\displaystyle L}$에 대해$.$

정규 언어의 클래스는 동형식과 역동형성으로 폐쇄된다.^[5]마찬가지로, 문맥 없는 언어는 동형식과^{[note 3]} 역동형성에 의해 폐쇄된다.^[6]

문자열 동형문자는 $알파벳{\displaystyle }$ $alphabet{\displaystyle \mathrm{}}$ {\$displaystyle f(a)\neq \varepsilon }$에 대한 f$$( )${\displaystyle }$) ${\displaystyle \ne }$ { ${$ { { $\displaysty \Sigma }.$ 간단한$$한 글자 대체 암호는 ( hom-free) 문자열 동형문자의 예다.

문자열 동형상 g는_uc 위의 대체와 유사한 것을 정의함으로써 얻을 수 있다: g(‹a_uc‹) = ‹A›, ..., g_uc(‹0›) = ε. 그러나 구두점 문자에 g를_uc 정의하지 않도록 한다.역동형 영상의 예는 다음과 같다.

• g_uc⁻¹_uc({ ‹SS› }) = { ‹sss,, ssß,, ‹ßs› }}, g(ssss)) = g_uc(ssß) = g(ssß) = g_uc(ss›) = ‹SS› }, 그리고
• g_uc⁻¹({ ‹A›, ‹bb› }}) = { ‹a› }, g_uc(‹a›) = ‹A›, ‹b›은 g로 도달할 수 없기 때문에 ga_uc› }.

후자 언어의 경우_uc g_uc⁻¹_uc({ ‹A›, ‹bb› }) = g({ ‹a› }}) = { ‹A› } { ‹A›, ‹b› }.동형상 g는_uc ‹0›을 ε에 매핑하기 때문에 ε이 없는 것이 아니다.

각 문자를 단지 문자로 매핑하는 매우 간단한 문자열 동형상주의 예는 EBCDIC로 인코딩된 문자열을 ASCII로 변환하는 것이다.

문자열 투영

If s is a string, and ${\displaystyle \Sigma }$ is an alphabet, the string projection of s is the string that results by removing all characters that are not in ${\displaystyle \Sigma }$. It is written as ${\displaystyle \pi _{\Sigma }(s)\,}$. It is formally defined by removal of characters from the right hand측면:

${\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\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{cases}}}$

여기서 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon }$은(는) 빈 문자열을 나타낸다$$.문자열의 투영은 관계 대수에서의 투영과 본질적으로 동일하다.

문자열 투영은 언어 투영으로 승격될 수 있다.공식 언어 L을 지정하면, 그 투영은 다음에서 주어진다.

${\displaystyle \pi _{\Sigma }(L)=\\{\pi _{\Sigma }\vert \s\in L\}}}$^{[필요하다]}

오른쪽 지수

문자열 s에서 문자 a의 오른쪽 몫은 문자열 s에서 문자 a의 잘림이다.$s{\displaystyle }$/ ${\displaystyle a}$ ${\displaystyle s/a}$로 표시되며$,$ 문자열 오른쪽에 a가 없으면 빈 문자열로 표시된다.따라서 다음과 같다.

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

빈 문자열의 몫은 다음과 같다.

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

마찬가지로, 모노이드 $M{\displaystyle }$ ${\displaystyle M}$의 부분 집합 $S{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle M}$ ${\displaystyle S\subset M}$을(를) 고려할 때, 하나의 몫의 부분 집합은 다음과 같이 정의할 수 있다$.$

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

왼쪽 인용구는 문자열의 왼쪽에서 작업이 수행되는 경우와 유사하게 정의될 수 있다.^{[citation needed]}

Hopcroft와 Ulman(1979)은₂ L/L₁ = { s ∃t∈L₂. st∈L₁}^[7]과 같은 알파벳에 걸쳐 L과₁ L 언어의₂ 몫 L₁/L을₂ 정의한다.문자열 s와 구별되는 문자 a, b, Hopcroft 및 Uullman의 정의는 {sa} / {b}이(가) { ε }이(가) 아닌 {}을(를) 양보한다는 것을 의미하기 때문에 위의 정의의 일반화는 아니다.

단일톤 언어 L과₁ 임의 언어 L의₂ 왼쪽 지수(Hopcroft 및 Ulman 1979년과 유사하게 정의되었을 때)는 Brzozowski 파생상품으로 알려져 있다. 만약 L이₂ 정규 표현으로 표현된다면, 왼쪽 몫이 될 수 있다.^[8]

통사적 관계

모노이드 $M{\displaystyle }$ ${\displaystyle M}$의 부분 집합 ${\displaystyle S}$ ${\displaystyle \subset }$ M ${\displaystyle S\subset M}$의 오른쪽 지수는 S의 오른쪽 구문 관계라고 하는 동등성 관계를 정의한다$$.그것은 에 의해 주어진다.

$\displaystyle \sim _{S}\,=\,\{(s,t)\in M\times M\\\\\vert \S/s=S/t\}}$

가족 권리 인수가 유한한 경우에만, 즉 가족 권리 인수가 유한한 경우에만, 그 관계는 분명히 유한 지수(등가 등급의 유한한 수)이다.

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

유한하다.M이 일부 알파벳을 넘는 단어의 모노이드인 경우에, S는 그 때 정규 언어, 즉 유한 상태 자동화에 의해 인식될 수 있는 언어다.이것은 통사적 모노이드에 관한 글에서 더 자세히 논의된다.^{[citation needed]}

권리취소

문자열 s에서 문자 a를 올바르게 취소하는 것은 문자열 s에서 문자 a가 처음 발생하는 것을 오른쪽에서 시작하여 제거하는 것이다.${\displaystyle s}$ ${\displaystyle ÷}$ a ${\displaystyle s\div a}$로 표시되며$$, 재귀적으로 정의된다.

${\displaystyle (sa)\div b={\div}s&{\\mbox{{a=b\\(s\div b)a&{a}neq b\end{case}}}}}$

빈 문자열은 항상 취소할 수 있음:

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

명확한 취소 및 예상 통근:

${\displaystyle \pi _{\Sigma }\div a=\pi _{\Sigma }(s\div a)}$^{[필요하다]}

접두사

문자열의 접두사는 문자열의 모든 접두사 집합이며, 지정된 언어에 대한 경우:

${\displaystyle \operatorname {Pref} _{L}s}=\{t\\\\\vert \s=tu{\mbox{{}}}}{}}}}}}}$

$여기$서 s ${\displaystyle \in }$ ${\displaystyle L}$ ${\displaystyle s\in$ L$\}.$

언어의 접두사 폐쇄는

${\displaystyle \operatorname {Pref}(L)=\bigcup_{s\in L}\operatorname {Pref}_{L}=\lef\{t\\\\\vert \s=tu;s\in L;t,u\in \operatorname {Alf}^{*}\right\}}}}}}}}}}}}$

예:
${\displaystyle L=\ft\{abc\right\}{\mbox{}}{}}}\\opername {Pref}(L)=\left\{\varepsilon ,a,ab,abc\right\}}}}}$

${\displaystyle \mathrm{Pref}}$ ${\displaystyle }$ (${\displaystyle L}$)${\displaystyle }$= ${\displaystyle L}$ ${\displaystyle \operatorname {Pref}(L)=L}$인 경우 언어는 접두사 닫힘이라고 불린다$.$

접두사 폐쇄 연산자는 다음과 같은 IDempotent:

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

접두사 관계는 $s{\displaystyle }$relation Pref ${\displaystyle L_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle t}$) ${\displaystyle$ s\$sqsubseteq }$인 경우에만$$ $s{\displaystyle }$ ${\displaystyle ⊑}$ t ${\displaystyle s\$$s\in \operatorname {Pref} _{L}(t)$인 경우 } t ${\$${\displaystyle \mathrm{displaystyt}}$}인 이진 관계 입니다$.$이 관계는 접두사 주문의 특별한 예다.^{[citation needed]}

참고 항목

• 프로그래밍 언어(문자열 함수) 비교
• 리바이스 보조정리
• 문자열(컴퓨터 과학) — 문자열에서 보다 기본적인 작업의 정의 및 구현

메모들

참조

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages and Computation. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001. (제3장 참조)