[계산이론] Language, Grammars

Language

alphabet : 하나 이상의 symbol의 finite set

string : alphabet에 속하는 symbol의 finite sequence
ex) alphabet $\Sigma = { a, b }$이면 $abab$, $aaabbba$ 는 $\Sigma$의 string

concatenation of two strings $w$ $v$ : $v$의 symbol들을 $w$의 오른쪽 끝에 붙이는 것.
ex) $w = a_{1}a_{2}a_{3}$ and $v = b_{1}b_{2}b_{3}$ 이면, $wv = a_{1}a_{2} \cdots a_{n}b_{1}b_{2} \cdots b_{m}$.

reverse of a string $w$ : $w^{R} = a_{n} \cdots a_{2}a_{1}$

length of a string $w$ : Denoted by $|w|$. The number of symbols in the string.

empty string : A string with no symbols at all. Denoted by \lambda.
$$
|\lambda | = 0 \\
\lambda w = w \lambda = w
$$
The above hold for all $w$.

substring of $w$ : Any string of consecutive symbols in some $w$.

다음의 케이스에서,
$$
w = vu
$$
prefix : $v$
suffix : $w$

ex) If $w = abbab$, then ${ \lambda, a, ab, abb, abba, abbab }$ is the set of all prefixes of $w$.

$w^{n}$ stands for the string obtained by repeating $w$ $n$ times. We define $w^{0} = \lambda$ for all $w$.

$\Sigma$ 가 alphabet이라면 $\Sigma^{\ast}$는 $\Sigma$에서 0개 이상의 symbol을 concatenate한 string의 set.
$\Sigma^{\ast}$ 는 항상 $\lambda$를 포함.
Empty string을 제외한 집합을 위해 다음과 같은 정의를 사용한다.
$$ \Sigma ^{+} = \Sigma ^{\ast} - { \lambda }
$$
가정에 의해 $\Sigma$는 유한하지만 $\Sigma ^{\ast}$와 $\Sigma ^{+}$는 무한함에 유의(string의 길이에 제한은 없으므로.

Language $L$은 일반적으로 $\Sigma ^{\ast}$의 subset에서 정의된다.

$L$의 한 string은 $L$의 sentence로 불린다.

ex)
Let $\Sigma = { a, b }$. Then
$$
\Sigma ^{\ast} = { \lambda, a,b,aa,ab,ba,bb,aaa,aab, ... }.$$
The set ${a, aa,aab }$ is a language on $\Sigma$. (Finite language case)
$L = { a^{n} b^{n} : n \ge 0 }$ is also a language on $\Sigma$ (Infinite language case)

The complement of a language is defined with respect to $\Sigma^{\ast}$ : $\bar{L} = \Sigma ^{\ast} - L$
The reverse of a language is the set of all string reversals. : $L^{R} = { w^{R} : w \in L }$
The concatenation of two languages $L_{1}$ and $L_{2}$ : $L_{1} L_{2} = {xy : x \in L_{1}, y \in L_{2} }$.
We define $L^{n}$ as $L$ concatenated with itself $n$ times. $L^{0} = { \lambda }$ and $L^{1} = L$ for every language $L$.

We define star-closure of a language as $L^{\ast} = L^{0} \cup L^{1} \cup L^{2} \cdots$ and
positive closure as $L^{+} = L^{1} \cup L^{2} \cdots $

Grammars

영어에서 sentence는 다음과 같이 분해해나감으로써 표현할 수 있다.
$\langle \textit{sentence} \rangle \rightarrow \langle \textit{noun_phrase} \rangle \langle \textit{predicate} \rangle$
$\langle \textit{noun_phrase} \rangle \rightarrow \langle \textit{article} \rangle \langle \textit{noun} \rangle$,
$\langle \textit{predicate} \rangle \rightarrow \langle \textit{verb} \rangle$
이러한 개념을 통해 formal grammar의 아이디어를 얻을 수 잇다.

---

def)
A grammar $G$ is defined as a quadruple
$$
G = (V,T,S,P),
$$
where $V$ is a finite set of objects called variables,
$T$ is a finite set of objects called terminal symbols,
$S \in V$ is a special symbol called the start variable,
$P$ is a finite set of productions.
It will be assumed without further mention that the sets $V$ and $T$ are nonempty and disjoint.

---

모든 procution rule은 $x \rightarrow y$의 형태를 가지고 $x \in (V \cup T) ^{+}$와 $y \in (V \cup T)^{\ast}$이라고 가정.

String $w$에 production을 적용하여 string $z$를 얻게 되면 $w \Rightarrow z$로 표기하고, $w$가 $z$를 derive한다고 표현한다.

만약 $w_{1} \Rightarrow w_{2} \Rightarrow \cdots \Rightarrow w_{n}$이면 $w_{1}$이 $w_{n}$을 derive한다고 하고, $w_{1} \overset{\ast} \Rightarrow w_{n}$

주어진 grammar에서 production rule을 적용하는 순서에 따라 보통 여러 string을 생성할 수 있는데, 그러한 모든 string의 set을 grammar에 의해 생성되는 or 정의되는 language라고 한다.

---

def)
Let $G = (V,T,S,P)$ be a grammar. Then the set
$$
L(G) = \left\{ w \in T^{\ast} : S \overset{\ast} \Rightarrow w \right\}
$$
is the language generated by $G$.

---

$w \in L(G)$ 이면 $S \Rightarrow w_{1} \Rightarrow w_{2} \Rightarrow \cdots \Rightarrow w_{n} \Rightarrow w$를 sentence $w$의 derivation이라고 부른다.

$S$, $w_{1}$, $w_{2}$, $\cdots$, $w_{n}$와 같이 terminal이나 variable을 담고 있는 것들은 sentential forms 라고 부른다. (꼭 variable을 포함해야 하는 것은 아니다)

두 개의 문법 $G_{1}$과 $G_{2}$가 같은 언어를 생성하는 경우이면,($L(G_{1} = L(G_{2})$) $G1$ and $G2$ are equivalent.