• THREE BASIC CONCEPTS
  • 세 가지 기초 개념
    • 언어(languages)
    • 문법(grammars)
    • 오토마타(automata)

언어(Languages)

알파벳(alphabet)

  • 하나 이상의 symbol들의 유한집합.
    • 문자들의 집합.
  • alphabet은 \(\sum\) 기호로 나타낸다.

예를 들어 a부터 z까지의 알파벳을 쓰는 언어는 다음과 같이 나타낼 수 있다.

\[\sum = \{ a, b, c, ..., z \}\]

문자열(string)

  • string은 주어진 알파벳에 속한 symbol들의 유한 길이의 순서열이다(finite sequences of symbols from the alphabet).

앞으로 예를 들 때에는 주로 다음을 사용할 것이다.

  • 알파벳으로 \(\sum = \{ a, b, c, ... \}\)
  • 문자열 이름으로 \(u, v, w\)
    • 예: 문자열 \(w = aabbac\)

문자열 접합(string concatenation)

string w와 string v가 있을 때, wv라고 쓰면, 두 string을 붙인 것이다.

  • w의 오른쪽 끝에 v의 symbols를 이어 붙이면 된다.
    • w = abc 이고 v = def 이면, wv = abcdef이다.
\[\begin{align} w & = a_1 a_2 ... a_n \\ v & = b_1 b_2 ... b_m \\ wv & = a_1 a_2 ... a_n b_1 b_2 ... b_m \\ \end{align}\]

역 문자열(reverse string)

  • 문자열의 순서를 뒤집은 문자열이다.
\[w^R = a_n ... a_2 a_1 \\\]

string length

  • string w의 length는 | w | 로 표시한다.
\[| uv | = | u | + | v |\]

빈 문자열(empty string)

  • 길이가 0인 빈 문자열을 \(\lambda\)로 표기한다.
\[\begin{align} | \lambda | & = 0 \\ \lambda w & = w \lambda = w \\ \end{align}\]

부문자열(substring)

  • 문자열 w 내에 존재하는 연속적인 문자들의 문자열.

다음과 같은 string w가 있다고 하자.

\[w = vu\]
  • string v와 string u는 w의 substring이다.
  • substring v를 string w의 전위부(prefix)라 한다.
  • substring u를 string w의 후위부(suffix)라 한다.

반복(repeating)

  • \(w^n\)은 string w를 n번 반복한 것이다.
  • 따라서, \(w^0 = \lambda\)

모든 문자열의 집합 \(\Sigma^*, \Sigma^+\)

  • \(\Sigma^*\): \(\Sigma\)에 속한 symbols를 0개 이상 concat해서 얻은 모든 문자열의 집합.
  • 문자가 0개인 string도 모든 문자열의 집합에 포함된다. \(\lambda \in \Sigma^*\)

그리고 모든 문자열의 집합에서 빈 문자열을 제외한 집합을 \(\Sigma^+\)라 한다.

\[\Sigma^+ = \Sigma^* - \{ \lambda \}\]
  • \(\Sigma^+, \Sigma^*\)는 항상 무한 집합이다.
  • 시그마 스타, 시그마 플러스라고 읽자.

언어

  • 언어는 일반적으로 \(\Sigma^*\)의 부분집합으로 정의된다.
    • 언어는 집합이다.
  • 어떤 언어 L에 포함되는 string을, language L의 sentence라 부른다.

언어 L의 여집합(complement of L)

\[\overline{L} = \Sigma^* - L\]
  • 언어 L의 여집합 = 모든 문자열의 집합에서 언어 L 집합을 뺀 것.

언어 L의 역(reverse of L)

\[L^R = \{ W^R : w \in L \}\]
  • 언어 L의 역: 언어 L에 속하는 모든 문자열(sentence)들을 reverse한 문자열들의 집합.

언어의 접합

  • 언어 \(L_1\)과 언어 \(L_2\)의 concat은 \(L_1\)과 언어 \(L_2\)의 모든 원소를 concat하여 얻을 수 있는 모든 sentence의 집합.
\[L_1 L_2 = \{ xy : x \in L_1, y \in L_2 \}\]

언어 L을 n번 concat 한 결과를 \(L^n\)이라 부른다.

\[\begin{align} L^0 & = \{ \lambda \} \\ L^1 & = L \\ \end{align}\]

언어 L에 대한 스타 페포(star-closure)는 다음과 같이 정의한다.

\[L^* = L^0 \cup L^1 \cup L^2 ...\]

언어 L에 대한 양성 폐포(positive-closure)는 다음과 같이 정의한다.

\[L^+ = L^1 \cup L^2 ...\]

문법(Grammars)

문법 G는 다음과 같은 네 원소 쌍(quadruple)으로 정의된다.

\[G = (V, T, S, P)\]
  • V: 변수(variables)라 부르는 객체들의 유한 집합.
    • 영어로 비유하자면 주어, 동사, 형용사…
    • 공집합이 아니다.
  • T: 단말 심벌(terminal symbols)이라 불리는 객체들의 유한 집합.
    • 단어들.
    • 공집합이 아니다.
  • S: 시작 변수(start variable). V의 원소인 특별한 심벌이다.
    • V 중에서 특별히 시작할 때 사용하는 것들.
  • P: 생성규칙들(productions)의 유한집합.
    • 우리가 일반적으로 문법이라 부르는 것. 문법 구조.
  • V와 T는 서로소임을 가정한다.

생성 규칙

  • 생성 규칙이 문법의 핵심.
    • 하나의 string을 다른 string으로 변환하는 방법을 규정한다.

생성규칙은 다음의 형태를 갖는다.

\[x \rightarrow y\]

이 때, x와 y는 각각 다음과 같이 집합의 원소이다.

  • \(x \in (V \cup T)^+\) 이다.
  • \(y \in (V \cup T)^*\) 이다.

생성 규칙의 적용

string w가 다음과 같이 있다고 하자.

\[w = uxv\]

string w에 생성규칙 \(x \rightarrow y\)를 적용해서 다음과 같은 string z을 얻었다고 하자.

\[z = u\color{red}yv\]

이러한 과정을 다음과 같이 표현하자.

\[w \Rightarrow z\]

이에 대해 다음과 같이 표현할 수 있다.

  • w가 z를 유도한다(w derives z).
  • z가 w로부터 유도된다(z is derived from w).

Successive strings are derived by applying the productions of the grammar in arbitrary order. A production can be used whenever it is applicable, and it can be applied as often as desired.

  • 생성규칙을 임의로 적용하여 문자열을 만들 수 있다.
  • 생성규칙은 적용 가능하면 언제든지 사용할 수 있고, 필요한 만큼 여러 번 적용할 수 있다.

다음과 같이 유도할 수 있다면,

\[w_1 \Rightarrow w_2 \Rightarrow ... \Rightarrow w_n\]

\(w_1\)이 \(w_n\)을 유도한다고 말한다(we say that \(w_1\) derives \(w_n\)).

그리고 다음과 같이 표기한다.

\[w_1 \overset{*}{\Rightarrow} w_n\]

*은 \(w_1\)에서 \(w_n\)을 유도하기까지 \(0 \sim n\)단계를 거칠 수 있음을 의미한다.

언어 L(G)

문법 \(G = (V,T,S,P)\)으로 생성되는 언어 \(L(G)\)를 다음과 같이 정의한다.

\[L(G) = \{ w \in T^* : S \overset{*}{ \Rightarrow } w \}\]
  • w : string w (sentence)
  • \(T^*\) : 단말 심벌을 0~n 번 concat 한 string의 집합.
  • S : 시작 변수

만약 \(w \in L(G)\)이면…

\[S \Rightarrow w_1 \Rightarrow w_2 \Rightarrow ... \Rightarrow w_n \Rightarrow w\]

을 문장 w에 대한 유도(derivation)라 부른다.

  • \(w_1, w_2, ..., w_n\) : 이 유도에서의 문장 형태(sentential form).

예제 1.11

다음과 같은 문법 G와 생성 규칙 P가 있다고 하자.

\[\begin{align} G & = ( \{ S \}, \{ a, b \}, S, P ) \\ P & = \{ \\ & S \rightarrow aSb, \\ & S \rightarrow \lambda \\ \} & \\ \end{align}\]

다음과 같은 유도(derive)가 가능하므로

\[\begin{align} S & \Rightarrow aSb \Rightarrow ab \\ S & \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb \\ \end{align}\]

다음과 같이 표기할 수 있다.

\[\begin{align} S & \overset{*}{ \Rightarrow } ab \\ S & \overset{*}{ \Rightarrow } aabb \\ \end{align}\]
  • string ab, aabb는 G에 의해 생성되는 언어에 속한 문장이다.
  • aSb, aaSbb는 문장 형태이다.

이 문법 G는 \(a^n b^n\) 형태의 string만을 유도한다.

\[S \overset{*}{ \Rightarrow } a^n S b^n \Rightarrow a^n b^n\]

예제 1.12

문제: 다음 언어를 생성시키는 문법을 찾아라.

\[L = \{ a^n b^{n+1} : n \ge 0 \}\]

답.

\[\begin{align} G & = ( \{ S, A \}, \{ a, b \}, S, P ) \\ P & = \{ \\ & S \rightarrow Ab, \\ & A \rightarrow aAb, \\ & A \rightarrow \lambda \\ \} & \\ \end{align}\]

시작부터 오른쪽에 b 가 붙어있고, 그 외의 생성규칙은 예제 1.11과 같다.

문법의 동치

\(L(G_1) = L(G_2)\) 이면 두 문법 \(G_1\)과 \(G_2\)는 동치(equivalent)라 할 수 있다.

즉, 두 개의 문법 \(G_1\)과 \(G_2\)가 같은 언어를 생성한다면, 두 문법은 동치이다.

오토마타(Automata)

오토마타/오토마톤의 뜻

  • 오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.

사전도 찾아보자

  • au·tom·a·ta | ɔːtɑ́mətə | -tɔ́m- | 명사 automaton의 복수형.
  • au·tom·a·ton | ɔːtɑ́mətɑ̀n | -tɔ́mətn | 명사(『복수』 automatons, -ta | -tə | ) [불]
    1. 자동적으로 움직이는 것; 오토마톤, 자동 인형; （기계의） 자동 장치.
    2. 기계적으로 행동하는 사람.
    3. 〔컴퓨터〕 오토마톤, 자동 장치: 미리 정해진 조작이나 명령에 자동으로 반응하는 기계나 제어 장치.

오토마톤의 필수 기능

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

입력을 읽는 장치

  • 입력은 주어진 알파벳으로 이루어진 string이며, input file에 기록되어 있다.

  • 입력을 읽을 수만 있고, 수정은 할 수 없다.

  • 입력 파일은 하나하나의 셀(cells)로 이루어져 있다.
    • 하나의 셀은 딱 하나의 문자(symbol)만 갖는다.
  • 입력 장치(input mechanism)
    • 입력 파일을 왼쪽에서 오른쪽으로 읽는다.
    • 한번에 한 글자만 읽을 수 있다.
    • end-of-file을 감지하는 방식으로 input string의 끝을 알(detect) 수 있다.

임시 저장 장치

  • 오토마톤은 임시 저장 장치를 갖는다.
    • 임시 저장 장치는 무한히 많은 셀로 이루어져 있다.
    • 셀 하나는 하나의 symbol을 저장할 수 있다(입력 알파벳과 꼭 같아야만 하는 것은 아니다).
  • 오토마톤은 저장용 셀을 읽을 수 있고, 값을 변경할 수도 있다.

참고: 임시 저장 장치의 성질에 따라 여러 유형의 오토마타로 구분할 수 있다.

제어 장치

  • 오토마톤은 제어 장치(control unit)를 갖는다.
    • 제어 장치는 하나의 상태를 갖는다.
    • 상태는 유한한 수의 내부 상태 중 하나이다.
    • 상태는 사전에 정의된 규칙(some defined manner)에 따라 바뀔 수 있다.
  • 오토마톤은 이산 시간 단위(discrete timeframe)로 작동하는 것으로 가정한다.
  • 임의의 시간에, 제어 장치는 특정한 내부 상태를 갖는다.

  • 임의의 시간에, 입력 장치는 입력 파일의 문자 하나를 읽는다.

  • 제어 장치의 내부 상태는 다음 단계에서, 다음 단계 함수/전이 함수(next-state or transition function)에 의해 결정된다(바뀔 수 있다).
  • 전이 함수는 다음 상태를 결정할 때 다음의 사항들을 참고한다.
    • 현재 상태
    • 입력 문자
    • 임시 기억장소에 저장된 내용
  • 다음 단계로 넘어가는 동안
    • 출력을 발생시킬 수 있다.
    • 임시 기억장소의 정보가 변경될 수 있다.
  • configuration(형상) : 이 용어는 다음을 언급할 때 사용한다.
    • 제어 장치의 상태
    • 입력 파일의 상태
    • 임시 기억장소의 상태
  • 오토마타가 한 config로부터 다음 config으로 전이하는 것을 이동(move)이라 한다.

결정적 오토마타와 비결정적 오토마타

  • 결정적 오토마톤(deterministic automaton)
    • 각 이동이 현재의 config에 의해 유일하게 결정된다.
    • 오토마타의 내부 상태, 입력, 임시 저장소의 내용만 알면 오토마타의 미래의 행동을 정확히 알 수 잇다.
  • 비결정적 오토마톤(nondeterministic automaton)
    • 각 단계에서 여러 가지의 이동 방법을 갖는다.
    • 따라서 가능한 행동들의 집합을 예측할 수 있을 뿐이다.

인식기와 변환기

  • accepter(인식기)
    • 출력이 yes, no 로만 제한되어 있는 오토마톤.
    • 입력 string에 대해, accepter는 accept 또는 reject만 할 수 있다.
  • transducer(변환기)
    • 출력으로 string을 생성할 수 있는 오토마톤.