[계산이론] - (1) 언어, 문법, 오토마타

 

 

 

 

 

언어 (Languages)

우리들은 이미 자연 언어(natural languages)를 사용하고 있으며, 이러한 개념과는 친숙합니다.

그러나 "언어"라는 단어에 대해서 설명을 하라고 한다면, 이는 생각보다 어려울 것입니다.
언어라는 단어를 검색해보면 사실, 개념들을 표현할 수 있도록 해 주는 심벌(symbol)들의 집합과, 심벌을 다루는 규칙들의 집합을 수반하는 시스템이라 비공식적인 정의를 내리고 있습니다.

 

 

 

 

 

 

 

 

심벌(symbol, 기호) 혹은 단말 심벌(terminal symbol)

a, b, c, .. 등과 같은 기호들입니다.

 

 

 

 

 

 

 

 

 

알파벳(Alphabet)

알파벳이란 하나 이상의 심벌들의 유한 집합이며, 보통 $\Sigma$로 표현합니다.

 

 

 

 

 

 

 

 

 

 

문자열(string)

주어진 알파벳에 속한 심벌들을 나열하여 문자열(string)을 만들 수 있습니다.

알파벳이 $\Sigma  = \left\{ a,b\right\}$ 라면, abab나 aaaabbaa등은 알파벳 $\Sigma$ 에 대한 문자열이 됩니다.

앞으로 특별한 경우를 제외하고는 알파벳의 원소로는 소문자 a, b, c 등을 사용할 것이고, 이러한 알파벳을 사용하며 만들어지는 문자열은 u, v, w등의 기호를 사용하겠습니다.

$w = abaaa$ 는 이름이 w인 문자열의 값이 abaaa임을 나타냅니다.

 

 

 

 

 

 

 

 

 

 

 

접합(concatenation)

문자열 w의 오른쪽에 문자열 v를 이어 붙여 만들어지는 문자열입니다.

다음과 같이 표기합니다.

$$wv$$

예를 들어 $w = aabb$ , $v = bbcc$ 인 경우, $wv = aabbbbcc$ 입니다.

 

 

문자열 w에 대해, w를 n번 반복하여 얻어지는 문자열은 다음과 같습니다.

$$w^{n} = ww \cdots w$$

 

이때 n이 0인 경우에는 $\lambda$ 기호를 사용하여 표현합니다.

$$w^{0} = \lambda $$

 

 

 

 

 

 

 

 

 

 

 

역 문자열(reverse string)

문자열 내의 심벌들을 역순으로 배열함으로써 얻어지는 문자열입니다. 다음과 같이 표현합니다.

$$w^{R}$$

$w = aabb$ 인 경우 $w^{R} = bbaa$  입니다.

 

 

 

 

 

 

 

 

 

 

 

 

길이와 빈 문자열 (Length & empty string)

문자열의 길이는 해당 문자열을 이루는 심벌들의 개수이며, $|w|$ 로 표기합니다. 

또한 문자열의 길이가 0인, 즉 문자를 전혀 갖지 않는 문자열을 빈 문자열이라 하며 다음과 같이 표기합니다.

$$\lambda$$

 

 

 

 

 

 

 

 

 

 

 

 

부문자열과 전위부, 후위부 (substring & prefix, suffix)

임의의 문자열 w내에 존재하는 연속적인 문자들의 문자열을 부문자열이라 합니다.

또한 임의의 문자열 w가 $w=vw$ 처럼 부문자열 u, v로 구성되어 있는 경우 부문자열 v와 u를 각각 문자열 w의 전위부(prefix), 후위부(suffix)라 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

클로져(혹은 폐포) (closure)

임의의 알파벳 $\Sigma$ 에 대해, $\Sigma$에 속한 심벌들을 0개 이상(0 포함)접합하여 얻어지는 모든 문자열들의 집합을 다음과 같이 표기합니다.

$$\Sigma^{*}$$ 

이는 시그마의 클로져(혹은 시그마의 스타-폐포) 읽습니다.

 

 

또한 시그마의 클로져는 항상 람다( $\lambda$ )를 포함하며, 시그마의 클로져에서 람다를 제외한 집합을 다음과 같이 표기합니다.

$$\Sigma^{+}$$ 

이는 시그마의 포지티브 클로져(혹은 시그마의 양성-폐포)(positive closure of $\Sigma$ )라고 읽으며, 다음과 같이 정의됩니다.

$$\Sigma^{+} = \Sigma^{*} - \left\{ \lambda \right\}$$

 

 

 

 

 

 

 

 

 

 

 

 

언어(Language)

가정에 의하여 알파벳 $\Sigma$ 는 유한 집합이지만, $\Sigma^{*}$ 과 $\Sigma^{+}$ 는 항상 무한 집합이 됩니다.

언어란 일반적으로 $\Sigma^{*}$의 부분집합으로 정의되며, 기호로는 L을 사용합니다.

 

 

 

 

 

 

 

 

 

 

 

 

문장(Sentence)

임의의 언어 L에 속하는 문자열(string)을 언어 L의 문장(sentence)이라 합니다.

 

 

 

 

 

 

 

 

 

 

여집합

언어들은 집합들이기 때문에, 두 언어에 대한 합집합, 교집합, 차집합 등이 정의될 수 있습니다.

또한 언어의 여집합은 $\Sigma^{*}$ 를 기준으로 정의됩니다.

$$\overline{L} = {\Sigma}^{*} - L $$

 

 

 

 

 

 

 

 

 

언어어 대한 접합

언어 L1과 L2를 접합하는 것은 다음과 같습니다.

$$L_1L_2 = \left\{ xy\; |\; x \in L_1 \;\; and \;\; y \in L_2 \right\}$$

 

어떤 언어 L을 n번 접합하여 얻어지는 언어를 다음과 같이 정의합니다.

$$L^n = LL\cdots L$$

 

또한 n이 0이거나 1인 특별한 경우 다음과 같이 정의됩니다.

$$ L^0 =  \left\{  \lambda \right\} $$
$$L^1 = L $$

 

 

 

 

 

 

 

 

 

 

 

 

언어에 대한 클로져

특정 언어 L에 대한 스타-폐포(star-closure)는 다음과 같이 정의되며,

$$L^* = L^0 \cup L^1 \cup L^2 \cup  \cdots $$

 

양성-폐포(positive-closure)는 다음과 같이 정의됩니다.

$$L^+ = L^1 \cup L^2 \cup  \cdots $$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문법 (Grammer)

문법은 기호로 G를 사용하며, 다음과 같은 네 원소 쌍으로 정의됩니다.

$$G = (V, \;\;T,\;\; S,\;\; P)$$

V(Variable)대신 N(Nonterminal)을 사용할 수도 있습니다.

 

$V$ 또는 $N$      :  변수(variable)혹은 Nonterminal symbol이라 불리는 객체들의 유한 집합입니다.
$T$                  :  단말 심벌(terminal symbol)이라 불리는 객체(알파벳)들의 유한 집합입니다.
$S$                  :  $V$ 에 속하는 특별한 심벌이며, 시작 변수(start variable)라 불립니다.
$P$                  :  생성규칙(production rule)들의 유한 집합입니다.

 

모든 생성규칙들은 다음의 형태를 가집니다.

 

$$\alpha \to \beta$$
단 $ \alpha \in (N \cup \Sigma )^{*}N(N \cup \Sigma )^{*} \;\;\; and \;\;\; \beta \in (N\cup \Sigma)^{*}$

$\alpha$ 의 위치에는 nonterminal 기호가 최소 1개는 들어와야 합니다.

 

 

 

 

 

 

 

 

 

 

 

유도(derive)

$w = uxv$ 이고

$z = uyv$ 일 때,

$x \to y$ 형태의 생성규칙을 w에 적용하여  z를 얻어낼 수 있으며 이를 다음과 같이 표현합니다.

$$w \Rightarrow  z $$

이에 대해 w가 z를 유도한다(derive)라고 읽습니다.

 

 

또한 다음과 같은 유도가 가능하다면,

$$w_1 \Rightarrow  w_2 \Rightarrow  w_3 \Rightarrow   \cdots \Rightarrow w_n$$

 

 

$w_1$ 이 $w_n$ 을 유도한다고 말하며, 다음과 같이 표기합니다.

$$w_1 \overset{*}{\Rightarrow} w_n $$

0번에 걸쳐 유도된다 하더라도 위와 같은 표현을 사용할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

문법이 생성하는 언어

생성규칙들을 서로 다른 순서로 적용하므로써, 주어진 문법은 많은 문자열들을 생성할 수 있습니다.

이러한 모든 단말 문자열들의 집합을 주어진 문법에 의해 생성되는 또는 정의되는 언어라 합니다.

 

즉 문법 $G = (V, T, S, P)$ 가 주어지면, 이에 의해 생성되는 언어 $L(G)$ 는 다음과 같이 정의됩니다.

$$L(G) = \left\{    w \in T^{*} : S \overset{*}{\Rightarrow} w \right\}$$

 

 

 

 

 

 

 

 

 

 

 

 

문장과 문장 형태(sentence & sentential form)

문장(sentence)은 언어(Language)에 속하는 스트링이라 하였습니다.

문장은 터미널 기호(terminal symbol)만으로 구성었습니다.

 

저희는 문법(Grammer)의 생성규칙을 통해 w라는 문장을 유도할 수 있으며, 이 과정을 다음과 같이 표현하였습니다.

$$S \Rightarrow w_1 \Rightarrow w_2 \Rightarrow  \cdots \Rightarrow w_n  $$

 

이 과정에서 나타나는 단말기호(terminal symbol)뿐만 아니라, 변수(variable)들로 구성된 문자열 $S$ , $w_1$ , $w_2$ , ..., $w_n$ 등을 이 유도에서의 문장 형태(sentential form)이라 합니다.

 

 

 

 

 

 

 

 

 

 

 

오토마타(automation)

오토마타란 디지털 컴퓨터에 대한 추상적 모델이며, 모든 오토마타들은 몇 가지 필수적인 기능을 갖습니다.

 

 

 

 

 

오토마타의 필수 기능

• 입력을 읽는 기능(mechanism for reading input)
• 임시 저장 장치(temporary storage device)
• 제어 장치(control unit)
• 출력 기능

 

 

 

 

입력 파일(input file)

오토마타는 입력 데이터를 읽을 수 있도록 입력을 받아들이는 장치를 갖습니다.

입력은 주어진 알파벳에 대한 문자열(string)이고 이는 입력 파일(input file)에 저장되며, 오토마타는 이를 읽을 수는 있으나 변경할 수는 없습니다.

입력 파일은 셀 단위로 구분되며, 각 셀은 하나의 심벌을 저장할 수 있습니다.

또한 오토마타는 출력 장치가 있어 어떠한 형태로든 출력을 생성할 수도 있습니다.

 

 

 

 

 

임시 기억장소(storage, 메모리)

오토마타는 임시 기억장소(storage)를 가질 수 있습니다. 이 기억장소는 무한개의 셀들로 구성되어 있으며 각 셀은 주어진 알파벳내의 한 심벌을 저장할 수 있습니다.

 

 

 

 

 

 

 

 

제어장치(control unit)

오토마타는 제어장치(control unit)를 가집니다.

이 제어 장치는 유한개의 내부 상태(internal state)들 중 한 상태에 있을 수 있으며, 미리 정해진 규칙에 따라 상태를 바꿀 수 있습니다.

 

오토마타는 이산(discrete) 시간 단위로 운영되는 것을 가정합니다.

임의의 주어진 시간에 제어 장치는 어떤 내부 상태에 있게 되며, 입력 장치는 입력 파일의 특정 심벌을 읽어들입니다.

 

 

 

 

 

 

 

 

 

전이 함수(transition function)

다음 단계에서의 제어 장치의 내부 상태는 다음 단계 함수(next-state function) 혹은 전이 함수(transtition function)에 의하여 결정됩니다.

이 전이 함수는 현재 상태, 현재의 입력 심벌, 현재 임시 기억장소에 저장된 내용 등에 따라 다음 상태를 결정합니다.

한 단계에서 다음 단계로 전이가 발생하는 동안 출력이 생성되거나 임시 기억장소의 내용이 변화될 수 있습니다.

 

 

 

 

 

 

 

 

 

형상(configuration) 과 이동(move)

제어 장치와 입력 파일, 그리고 임시 기억장소의 상태를 종합하여 언급할 때 사용합니다.

오토마타가 한 형상으로부터 다음 형상으로 전이하는 것을 이동(move)이라 합니다.

 

 

 

 

 

 

 

 

 

 

이후 글에서 유한 오토마타에 대해서 공부할텐데, 이때 오토마타를 결정적 오토마타(deterministic automata)와 비결정적 오토마타(nondeterministic automata)로 구분할 필요가 있습니다.

 

 

 

 

 

 

 

 

 

 

 

결정적 오토마타(Deterministic Automata)

결정적 오토마타에서는 각 이동이 현재의 형상에 의해 유일하게 결정됩니다.

즉 오토마타의 내부 상태, 입력, 그리고 임시 기억장소의 내용 등이 알려지면 그 오토마타의 이후 행동을 정확히 예측할 수 있게 됩니다.

 

 

 

 

 

 

 

 

 

 

비결정적 오토마타(Non-Deterministic Automata)

비결정적 오토마타에는 각 단계에서 여러가지 이동이 가능하며, 따라서 정확히 하나의 가능한 행동만을 예측하기보다는 가능한 행동들의 집합을 예측할 수 있을 뿐입니다.

 

 

 

 

 

 

 

 

 

 

 

인식기(Accepter)

출력이 단순히 "yes" 또는 "no"로 제한되어 있는 오토마타를 인식기(accepter)라 합니다.

인식기는 입력 문자열이 주어졌을 때, 그 문자열을 승인(accept)하거나 거부(reject)하는 역할만을 수행합니다.

 

인식기의 종류로는 유한 오토마타, 푸쉬다운 오토마타 등이 있습니다.

 

 

 

 

 

 

 

 

 

 

변환기(Transducer)

인식기보다 더 일반적인 오토마타로 임의의 문자열을 출력으로 생성할 수 있는 오토마타를 변환기(transducer)라 부릅니다.

변환기의 종류로는 밀리기계와 무어기계 등이 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

촘스키 위계 (Chomsky Hierachy)

언어를 생성하는 문법들의 생성규칙을 통해 문법을 분류한 것입니다.

 

총 4개의 타입이 있습니다.

 

 

 

 

 

무제한(unrestricted) 문법

생성규칙은 다음과 같습니다.

$$\alpha  \to \beta \;\;\; (\alpha \neq \lambda)$$

튜링 기계에 의해서 인식됩니다.

 

 

 

 

 

 

 

 

문맥연관(context-sensitive) 문법

생성 규칙은 다음과 같습니다.

$$\alpha A \beta \to \alpha \gamma \beta$$

 

단 $A \in N, \;\; \alpha , \beta \in (N \cup \Sigma)^{*}, \;\; \gamma \in (N \cup \Sigma)^{+}$

N은 variable 입니다.

 

 

즉 좌변은 variable(Nontermial Symbol)을 하나 이상 포함해야 하며 terminal symbol도 올 수 있고, 우변은 람다를 제외하고는 모두 허용됩니다.

 

 

이는 줄어들지 않는(non-contracting) 문법입니다.

$$\alpha \to \beta \;\;이때 \;\; |\alpha| \leq |\beta|$$ 

 

선형 한계 오토마타에 의해 인식됩니다.

 

(참고)

문맥에 연관되어 있다는 뜻은, 생성규칙의 좌변에서 'terminal symbol들이 어떻게 나타났는지'에 따라서 적용할 수 있는 규칙이 달라지므로, 즉 문맥에 연관되어 있으므로 문맥 연관이라 칭합니다.

 

 

 

 

 

 

 

 

 

 

 

 

문맥자유(무관)(context-free) 문법

생성 규칙은 다음과 같습니다.

$$A \to \alpha$$

이때 A는 하나의 변수(variable 혹은 Nonterminal Symbol)이며, 

α는  변수(Nonterminal Symbol)와 말단 기호(terminal symbol)들로 구성된 문자열입니다.

$$A \in N, \;\; \alpha \in (N \cup \Sigma)^{*} $$

즉 좌변에는 하나의 variable(Nontermial Symbol)만 올 수 있으며, terminal symbol은 올 수 없습니다.

 

푸쉬다운 오토마타에 의해 인식됩니다.

 

(참고)

문맥에 자유롭다는 뜻은, 생성규칙의 좌변에서 현재까지의 문맥, 즉 terminal symbol들이 어떻게 나타나있는지에 관계없이 생성규칙이 적용될 수 있다는 뜻입니다.

 

 

 

 

 

 

 

 

 

정규(regular) 문법

정규 문법은 우선형(right-linear)문법과 좌선형(left-linear) 문법의 총칭입니다.

 

 

우선형 문법의 생성 규칙은 다음과 같습니다.

$$  A \to xB   \;\;\; or \;\;\; A \to x \;\; (A, B \in N \;\; and \;\; x \in \Sigma^{*})$$

 

 

좌선형 문법의 생성 규칙은 다음과 같습니다.

$$A \to Bx \;\;\; or \;\;\; A \to x$$

 

유한 오토마타에 의해 인식됩니다.