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.
\(<br/>|\lambda | =
0 \\<br/>\lambda w = w \lambda = w<br/>\)
The above
hold for all $w$.
substring of $w$ : Any string of consecutive symbols in some $w$.
- 다음의 케이스에서,
- \(<br/>w = vu<br/>\)
- 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 }<br/>\)
가정에 의해
$\Sigma$는 유한하지만 $\Sigma ^{\ast}$와 $\Sigma ^{+}$는
무한함에 유의(string의 길이에 제한은 없으므로.
Language $L$은 일반적으로 $\Sigma ^{\ast}$의 subset에서 정의된다.
$L$의 한 string은 $L$의 sentence로 불린다.
ex)
Let $\Sigma = { a, b }$. Then
\(<br/>\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
\(<br/>G
= (V,T,S,P),<br/>\)
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
\(<br/>L(G)
= \left\{ w \in T^{\ast} : S \overset{\ast} \Rightarrow w
\right\}<br/>\)
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.