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

언어(Languages)

알파벳(alphabet)

We start with a finite, nonempty set Σ of symbols, called the alphabet.

  • 하나 이상의 symbol들의 유한집합.
  • alphabet은 기호로 나타낸다.

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

문자열(string)

From the individual symbols we construct strings, which are finite sequences of symbols from the alphabet.

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

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

  • 알파벳으로
  • 문자열 이름으로
    • 예: 문자열

문자열 접합(string concatenation)

The concatenation of two strings w and v is the string obtained by appending the symbols of v to the right end of w.

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

  • w의 오른쪽 끝에 v의 symbols를 이어 붙이면 된다.

역 문자열(reverse string)

The reverse of a string is obtained by writing the symbols in reverse order.

string length

The length of a string w, denoted by | w |, is the number of symbols in the string.

  • string w의 length는 | w | 로 표시한다.

빈 문자열(empty string)

We will frequently need to refer to the empty string, which is a string with no symbols at all. It will be denoted by λ.

  • 길이가 0인 빈 문자열을 로 표기한다.

부문자열(substring)

Any string of consecutive symbols in some w is said to be a substring of w.

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

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

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

반복(repeating)

If w is a string, then stands for the string obtained by repeating w n times.

  • 은 string w를 n번 반복한 것이다.
  • 따라서,

모든 문자열의 집합

If Σ is an alphabet, then we use Σ* to denote the set of strings obtained by concatenating zero or more symbols from Σ. The set Σ* always contains λ.

  • : 에 속한 symbols를 0개 또는 그 이상 concat해서 얻은 모든 문자열의 집합.
  • 문자가 0개인 string도 모든 문자열의 집합에 포함된다.

그리고 모든 문자열의 집합에서 빈 문자열을 제외한 집합을 라 한다.

  • 는 항상 무한 집합이다.
  • 시그마 스타, 시그마 플러스라고 읽자.

언어

A language is defined very generally as a subset of Σ*. A string in a language L will be called a sentence of L.

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

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

  • 언어 L의 여집합 = 모든 문자열의 집합에서 언어 L 집합을 뺀 것.

언어 L의 역(reverse of L)

  • 언어 L의 역: 언어 L에 속하는 모든 문자열(sentence)들을 reverse한 문자열들의 집합.

언어의 접합

The concatenation of two languages and is the set of all strings obtained by concatenating any element of with any element of .

  • 언어 과 언어 의 concat은 과 언어 의 모든 원소를 concat하여 얻을 수 있는 모든 sentence의 집합.

We define as L concatenated with itself n times.

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

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

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

문법(Grammars)

A grammar G is defined as a quadruple.

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

where V is a finite set of objects called variables,
T is a finite set of objects called terminal symbols,
S ∈ V is a special symbol called the start variable,
P is a finite set of productions.

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

It will be assumed without further mention that the sets V and T are nonempty and disjoint.

  • V와 T는 공집합이 아니며, 서로소임을 가정한다.

생성 규칙

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

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

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

  • 이다.
  • 이다.

생성 규칙의 적용

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

string w에 생성규칙 를 적용해서 다음과 같은 string 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.

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

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

을 유도한다고 말한다(we say that derives ).

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

*에서 을 유도하기까지 단계를 거칠 수 있음을 의미한다.

언어 L(G)

문법 으로 생성되는 언어 를 다음과 같이 정의한다.

  • w : string w (sentence)
  • : 단말 심벌을 0~n 번 concat 한 string의 집합.
  • S : 시작 변수

만약 이면…

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

  • : 이 유도에서의 문장 형태(sentential form).

예제 1.11

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

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

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

  • string ab, aabb는 G에 의해 생성되는 언어에 속한 문장이다.
  • aSb, aaSbb는 문장 형태이다.

이 문법 G는 형태의 string만을 유도한다.

예제 1.12

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

답.

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

문법의 동치

이면 두 문법 는 동치(equivalent)라 할 수 있다.

즉, 두 개의 문법 가 같은 언어를 생성한다면, 두 문법은 동치이다.

오토마타(Automata)

오토마타/오토마톤의 뜻

An automaton is an abstract model of a digital computer.

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

사전도 찾아보자

  • 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)

The automaton can produce output of some form.

  • 출력

입력을 읽는 장치

It has a mechanism for reading input. It will be assumed that the input is a string over a given alphabet, written on an input file, which the automaton can read but not change.

  • 입력은 주어진 알파벳으로 이루어진 string이며, input file에 기록되어 있다.
  • 입력을 읽을 수만 있고, 수정은 할 수 없다.

The input file is divided into cells, each of which can hold one symbol. The input mechanism can read the input file from left to right, one symbol at a time. The input mechanism can also detect the end of the input string (by sensing an end-of-file condition).

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

임시 저장 장치

It may have a temporary storage device, consisting of an unlimited number of cells, each capable of holding a single symbol from an alphabet (not necessarily the same one as the input alphabet). The automaton can read and change the contents of the storage cells.

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

As we will see, the nature of the temporary storage governs the power of different types of automata.

참고: 임시 저장 장치의 성질에 따라 여러 유형의 오토마타의 능력이 달라진다.

제어 장치

Finally, the automaton has a control unit, which can be in any one of a finite number of internal states, and which can change state in some defined manner.

  • 오토마톤은 제어 장치(control unit)를 갖는다.
    • 제어 장치는 하나의 상태를 갖는다.
    • 상태는 유한한 수의 내부 상태 중 하나이다.
    • 상태는 사전에 정의된 규칙(some defined manner)에 따라 바뀔 수 있다.

An automaton is assumed to operate in a discrete timeframe. At any given time, the control unit is in some internal state, and the input mechanism is scanning a particular symbol on the input file.

  • 오토마톤은 이산 시간 단위(discrete timeframe)로 작동하는 것으로 가정한다.
  • 임의의 시간에, 제어 장치는 특정한 내부 상태를 갖는다.
  • 임의의 시간에, 입력 장치는 입력 파일의 문자 하나를 읽는다.

The internal state of the control unit at the next time step is determined by the next-state or transition function. This transition function gives the next state in terms of the current state, the current input symbol, and the information currently in the temporary storage. During the transition from one time interval to the next, output may be produced or the information in the temporary storage changed. The term configuration will be used to refer to a particular state of the control unit, input file, and temporary storage. The transition of the automaton from one configuration to the next will be called a move.

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

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

A deterministic automaton is one in which each move is uniquely determined by the current configuration. If we know the internal state, the input, and the contents of the temporary storage, we can predict the future behavior of the automaton exactly.

  • 결정적 오토마톤(deterministic automaton)
    • 각 이동이 현재의 config에 의해 유일하게 결정된다.
    • 오토마타의 내부 상태, 입력, 임시 저장소의 내용만 알면 오토마타의 미래의 행동을 정확히 알 수 잇다.

In a nondeterministic automaton, this is not so. At each point, a nondeterministic automaton may have several possible moves, so we can only predict a set of possible actions.

  • 비결정적 오토마톤(nondeterministic automaton)
    • 각 단계에서 여러 가지의 이동 방법을 갖는다.
    • 따라서 가능한 행동들의 집합을 예측할 수 있을 뿐이다.

인식기와 변환기

An automaton whose output response is limited to a simple “yes” or “no” is called an accepter. Presented with an input string, an accepter either accepts the string or rejects it.

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

A more general automaton, capable of producing strings of symbols as output, is called a transducer.

  • transducer(변환기)
    • 출력으로 string을 생성할 수 있는 오토마톤.

Links