제10장 오토마타, 문법, 언어 오토마타 이론과 컴퓨터 관련 학문 오토마타와 관련된 3가지 개념 유한 오토마타 오토마타의 응용 제10장 오토마타, 문법, 언어 오토마타(Automata) 오토마타 이론과 컴퓨터 관련 학문 오토마타와 관련된 3가지 개념 유한 오토마타 오토마타의 응용 문법(grammar)과 언어(language) 튜링머신(Turing machine) 촘스키 포함 관계(Chomsky Hierarchy)

10.1 오토마타(Automata) ‘오토마타’(automata) 수학적 방법론에 바탕을 둔 디지털 컴퓨터의 추상적인 모델 디지털 컴퓨터의 수학적인 모델인 오토마톤(automaton)의 복수형 자동기계 장치 입력장치, 출력장치, 저장장치, 제어장치를 가지고 있음 현대적인 디지털 컴퓨터가 작동하는 이론적인 메카니즘 입력화일(input file) 제어장치(control unit) 출력(output) 저장장치(storage) [그림 10.1] 오토마타의 일반적인 구조

오토마타의 특성 오토마타는 입력 데이타를 읽을 수 있는 기능을 가지고 있음 특정 형태의 출력 기능을 가지고 있음 입력 데이터 입력 파일(input file): 네모꼴의 셀(cell)들로 이루어짐 각 셀에는 오직 하나의 심볼 (알파벳상의 스트링들) 씩만 존재 입력 파일의 왼쪽에서 오른쪽으로 심볼을 하나씩 차례로 읽음(파일의 끝까지) 입력 파일에 있는 내용을 읽는 것은 가능하지만 변경은 불가능 특정 형태의 출력 기능을 가지고 있음 0이나 1의 출력 ‘인식’(accept) 또는 ‘기각’(reject)의 출력도 생성할 수 있음 무한개의 셀들로 이루어진 임시 저장장치(storage device)를 가짐 각 셀은 하나의 심볼만을 가질 수 있음 작동에 따라 셀들의 내용을 읽어 내거나 변경할 수 있음 유한개의 내부 상태(internal states)를 제어할 수 있는 제어장치(control unit)를 가짐 이것의 제어에 따라 상태가 변화될 수 있음

기본 가정 이산적인(discrete time) 시간 단위로 작동됨을 기본 가정으로 함 어느 특정 시각에 제어장치는 특정의 상태에 놓여 있으며 입력 기능은 입력 화일상의 어떤 특정한 심볼을 읽는다. 제어장치의 다음 상태(next state)는 전이 함수에 의해 결정 전이가 이루어질 때에는 출력이 생성되거나 임시 저장 장치내의 심볼이 바뀜 전이 함수(transition function) 제어장치의 다음 상태 결정 현재의 제어 상태, 입력 심볼, 그리고 임시 저장장치내의 정보들에 의해 결정 ‘형상’(configuration) 제어장치, 입력 화일, 임시 저장장치들의 특정 시각에서의 상태들 ‘동작’(move) 한 형상에서 다른 형상으로의 전이

오토마타의 전이 방법 오토마타의 출력 여부 ‘결정적(deterministic) 오토마타’ 이동에 의한 다음 상태는 현재의 형상에 따라 유일하게 결정 현재의 내부 상태, 입력 심볼, 임시 기억장치에 관한 정보를 알면 오토마타의 다음 행동을 정확히 예측 ‘비결정적(nondeterministic) 오토마타’ 오토마타의 출력 여부 ‘인식기’(accepter) 입력스트링이 주어졌을 때 그 스트링을 인식하거나 기각할 수 있는 기능만을 가짐 ‘트랜스듀서’(transducer) 밀리 기계(Mealy Machine)와 같이 인식이나 기각의 기능 외에 출력도 낼 수 있는 오토마타 모델

10.2 오토마타 이론과 컴퓨터 관련 학문 오토마타를 학습하는 주된 이유 오토마타 이론을 통하여 컴퓨터와 관련된 이론적인 바탕과 작동의 원리를 보다 정확하게 이해함으로써 하드웨어나 소프트웨어 각 분야에 대한 직관을 넓힘 오토마타 이론의 직접적인 응용 디지털 컴퓨터의 디자인, 프로그래밍 언어, 컴파일러, 신경생리학, 통신, 신경망, 언어론 등 다양한 분야에 직접 활용 특히 컴파일러나 프로그래밍 언어를 정확하게 이해하기 위해서는 오토마타 이론의 이해가 필수적으로 요구

10.3 오토마타와 관련된 3가지 개념 오토마타 이론에서 가장 중요한 3가지 개념 언어(language) 문법(grammar) 오토마타 이론에서 가장 중요한 3가지 개념 언어(language) 문법(grammar) 오토마타(automata) 언어 문법 오토마타 [그림 10.2] 언어, 문법, 오토마타의 관계

언어(languages) 언어(Language) ‘알파벳’(alphabet) 유한 개의 공집합이 아닌 심볼들(symbols)의 집합 S 이들 심볼들로부터 스트링들(strings)이 만들어짐 유한 개의 시퀀스(sequence)로 이루어짐 Ex) 알파벳 S ={a,b}일 때 aa, ab, abab, bbaa 등은 S 상의 스트링이라고 볼 수 있음 w = abaaa 에서 w는 스트링을 나타내고 abaaa는 w의 특정한 값이 됨

정의 10.1 팰린드롬(palindromes)은 aba나 abba와 같이 앞에서 읽으나 뒤에서 읽으나 똑같은 스트링들을 말하는데 다음과 같이 정의될 수도 있다. (1) l(lamda) : 팰린드롬 (2) 만약 a가 임의의 심볼이면, 스트링 a는 팰린드롬 (3) 만약 a가 임의의 심볼이고 x가 팰린드롬이면 axa도 팰린드롬임 (4) 위의 (1)에서 (3)까지로부터 얻어지지 않는 어떤 것도 팰린드롬이 아님 정의 10.1

스트링에서의 연산과 정의 (a) 연결(concatenation) 두개의 스트링 w와 v를 연결하는 것 Ex) w = a1a2a3 ... an 이고 v = b1b2b3 …bn 일 때 w와 v의 연결: wv = a1a2a3 ...anb1b2b3 ...bn (b) 역(reverse) 어떤 스트링의 역순은 주어진 심볼들을 거꾸로 나열한 것 w = a1a2a3 ... an 이라면 그것의 역인 wR은 wR = an ...a3a2a1 이 된다. Ex) (cat)R = tac

정리 10.1 정리 10.1 스트링 w와 x에 대해 (wx)R = xRwR이 성립한다. (c) 접두사(prefix)와 접미사(suffix) 만약 w = vu라면 w의 접두사 : v w의 접미사: u Ex) banana에서 ba는 접두사이고 nana는 접미사이다. ‘서브스트링’(substring) 어떤 스트링에서 접두사나 접미사를 제거함으로써 이루어지는 스트링 Ex) nan은 banana의 서브스트링 ‘서브시퀀스’(subsequence) 주어진 스트링에서 0개 이상의 심볼을 제거함으로써 만들어짐 제거하는 심볼이 반드시 연속된 심볼일 필요는 없다. Ex) baaa나 bnn은 banana의 서브시퀀스 정리 10.1

(d) 스트링의 길이 (e) 스트링의 반복 스트링에 포함된 심볼의 개수 w와 같이 절대값을 써서 나타냄 |w| ‘공스트링’(empty string) 주어진 스트링이 어떠한 심볼도 가지고 있지 않음 (통상 l 로 나타냄) 따라서 | l |= 0이고 모든 w에 대해 l w = w l = w가 성립 u와 v가 스트링일 때 연결 uv의 길이에서 |uv| = |u| + |v|가 성립 (e) 스트링의 반복 w가 스트링일 때 wn이란 w를 n번 연결한 것 모든 w에 대해 w0 = l

[예제] 알파벳 ={a, b}에 대한 문자열 s1과 s2는 다음과 같다. s1=ababa s2=aabbaa 이때 s1s2와 |s1s2|를 구하여라. [풀이] s1s2=ababaaabbaa |s1|+|s2|=5+6=11이므로 |s1s2|=11이다.

(f) S*와 S+ S* Ex) S = {a, b}일 때 S*는 l를 항상 포함 Ex) S = {a, b}일 때 S* = {l, a, b, aa, ab, ba, bb, aaa, aab, ...} S+ S* 에서 l 를 제외한 경우 S+ = {a, b, aa, ab, ba, bb, aaa, aab, ...}

(g) 언어와 문장 언어(language): L ‘단어’(word) 또는 ‘문장’(sentence) ‘유한 언어’(finite language) 유한 개의 단어로 구성된 언어 Ex) S = {a, b}일 때 집합 {a, ab, aabb} ‘무한 언어’(infinite language) 단어의 개수가 무한개 Ex) S = {a, b}일 때 L = {anbn | n ≥ 0} ab나 aabb는 L의 단어 aa나 ba 등은 L에 속하지 않으므로 L의 단어가 아님

(h) 언어에서의 연산 언어는 단어들로 이루어진 집합 집합의 일반적인 연산이 가능 여집합(complement) 합집합(union), 교집합(intersection), 차집합(difference) 여집합(complement) L의 여집합은 로 나타내는데 L의 S* 에 대한 여집합 연결(concatenation) 두 개의 언어 L1과 L2의 연결은 L1의 어떤 원소와 L2의 어떤 원소를 차례로 연결하였을 때 표현되는 모든 스트링들의 집합 (순서에 유의) L

‘스타 클로우저’(star-closure) 또는 ‘클린 클로우저’(kleene closure) 언어 L이 n번 반복될 때는 Ln으로 표현 특히 모든 언어 L에 대해 L0 = {l } L1 = L, L2 = LL, Ln = Ln-1L 일 때 ‘스타 클로우저’(star-closure) 또는 ‘클린 클로우저’(kleene closure) L* = L0∪L1∪L2∪… 로 정의 ‘포지티브 클로우저’(positive closure) L*에서 L0를 제외한 것 L+ = L1∪L2∪……

10.4 유한 오토마타 유한 오토마타(FA: Finite Automata) 유한한 상태들의 집합과 ‘전이 함수’(transition function)들의 집합으로 구성 ( 임시 저장장치를 가지지 않음) ‘전이’ 알파벳 S 로부터 선택된 입력 심볼(input symbol)에 의해 생기는, 상태에서 상태로의 변화 입력 부호에 따라 상태는 항상 변할 수 있으며, 원래의 상태로 다시 돌아가는 전이도 있을 수 있음 [그림 10.3] 유한 오토마타

상태(state) 유한오토마타의 전이 방법 ‘시작 상태’(start state) 시작 상태에서 오토마타가 시작(보통 q0로 나타냄) 그래프에서는 서클로 표시(통상 앞에 작은 화살표를 그려서 표시) ‘최종 상태’(final state) 또는 ‘인식 상태’(accepting state) 그래프에서는 이중의 서클로 표시 유한오토마타의 전이 방법 결정적(Deterministic) 유한 오토마타 (DFA) 정규언어(regular language)에 대응 비결정적(Nondeterministic) 유한 오토마타 (NFA)

정의 10.2 결정적 유한 오토마타(Deterministic Finite Automata : DFA)는 다음과 같은 5개의 순서쌍으로 이루어진다. M =( , , , q 0, F) : 상태(state)들의 유한집합(finite set of states)  : 입력 알파벳(input alphabet)이라고 불리는 유한개의 심볼들의 집합  : x   인 전이 함수(transition function) q 0 : q 0 인 시작 상태 (start state) F : F  인 최종 상태의 집합(set of final states) 정의 10.2 O ~ O ~ O ~ O ~ O ~ O ~

DFA의 작동 개요 처음에는 시작 상태가 q0 에 있고 유한제어는 입력 스트링의 가장 왼쪽에 있는 심볼을 가리킴 오토마타의 작동에 따라 입력장치에서 한 심볼씩 오른쪽으로 이동하면서 상태가 바뀜 입력 메카니즘은 왼쪽에서 오른쪽으로의 방향으로만 이동이 가능 각 단계에서 하나씩의 심볼만을 읽을 수 있다는 점에 유의 스트링을 모두 읽고 난 후 DFA가 최종 상태에 있으면 그 스트링이 ‘인식되고’(accepted) 그렇지 않으면 ‘기각된다’(rejected).

예제 10.1 DFA M = ({q0, q1, q2}, {0, 1} , , q0, {q1}) 입력 스트링: 001, 0101, 1101, 00, 110, 011 ?? [그림 10.4] DFA의 예

a q0 q1 b b a b a q2  Transition diagram 예제 M = ({q0, q1, q2}, {a, b}, , q0, {q2}) (q0, a) = q1 (q0, b) = q2 (q1, a) = q2 (q1, b) = q0 (q2, a) = q0 (q2, b) = q1 입력 : aba 라면 (q0, a) = q1 (q1, b) = q0 (q0, a) = q1  no 입력 : ababb라면 (q1, b) = q1 (q0, b) = q2  yes a q0 q1 b b a b a q2  Transition Table

10.5 오토마타의 응용 예제 10.2 파스칼 언어에 있어서 모든 변수(identifier)들의 집합은 하나의 언어이다. 각 변수는 하나의 문자(letter)로 시작되어야 하며 문자 다음에는 임의 갯수의 문자나 숫자(digit)가 혼용하여 사용될 수가 있다. 다음의 문법은 변수에 대한 정확한 정의를 나타내는 규칙들이다. <id> → <letter><rest> <rest> → <letter><rest> | <digit><rest> | l <letter> → a | b | … | z <digit> → 0 | 1 | … | 9 예제 10.2

[그림 10.6] 파스칼에서의 변수를 인식하는 오토마타 이 문법에서 변수들로는 <id>, <letter>, <rest>, <digit>이며 터미날 심볼들은 a, b,… z, 0, 1, … 9 이다. 예를 들어 변수 x5의 유도 과정은 다음과 같다. <id> ⇒ <letter><rest> ⇒ x<rest> ⇒ x<digit><rest> ⇒ x5<rest> ⇒ x5 [그림 10.6] 파스칼에서의 변수를 인식하는 오토마타

10.6 문법(grammar)과 언어(language) 한가지 전형적인 예는 “문장에서는 명사절 다음에 서술어가 온다”의 경우를 들 수 있다. 이것을 보다 구체적으로 표현하면 <sentence> → <noun_phrase><predicate> 이것을 세분화하면 <noun_phrase> → <article><noun> <predicate> → <verb> 이것을 한번 더 세분화하면 <article> → A | The <noun> → girl | cat <verb> → swims | jumps 라고 한다면 “A girl swims” 또는 “The cat jumps” 등의 문장은 위의 문법에 맞는 문장이다.

[그림 10.7] 영어 문장 구조의 예 <sentence> <noun_phrase> <predicate> <article> <noun> <verb> A girl swims

문법(Grammar) 정의 10.3 문법 G는 다음과 같은 4개의 순서쌍(quadruple)으로 정의된다. G = (N, T, P, S) 1. N : ‘변수’(variable)라고 불리는 ‘넌터미날(nonterminal) 심볼’들의 유한 집합인데 통상 대문자 알파벳으로 표현. 2. T : ‘터미날(terminal) 심볼’ 의 유한 집합인데 통상 소문자 알파벳으로 표현 3. P : ‘생성규칙’(production rule)의 유한 집합인데 집합 P는 A → X1X2…XN 와 같이 표현된다. 여기서 A는 넌터미날이고 X1X2…XN 은 유한한 길이의 터미날 또는 넌터미날 심볼이다. 4. S : N에 속하는 ‘시작 심볼’(start symbol)로서 문장의 시작을 나타내며 통상 S를 사용한다. 정의 10.3

예제10.3 G = ({S, A}, {a, b, c}, P, S} 예제 10.3 P : S → abS S → aA A → c 여기서 {S, A} 는 넌터미날 심볼의 집합이고, {a, b, c}는 터미날 심볼의 집합이며, S는 시작 심볼이다. P에서 S → abS란 S로부터 오른쪽의 abS를 생성한다는 의미를 가지고 있다. 예제 10.3

정의 10.4 정의 10.4  는 ‘유도된다’(derived) 주어진 어떤 스트링에다 하나의 생성규칙을 적용하여 다른 스트링으로 변화하는 것 Ex) a  b 일 때 “a는 b를 유도한다” 또는 “b 는 a로부터 유도된다” 라고 표현 w → uav가 있을 때 w  ubv로 표현 w1  w2  …  wn : 0번 이상의 단계들로 유도된 것 : 특히 1번 이상 유도된 것을 나타낼 경우 정의 10.4

정의 10.5 정의 10.5 정의 10.6 정의 10.6 G = (N, T, P, S)가 문법일 때 ‘문장형태’(sentential form) w가 (N∪T)*에 속하는 경우 ‘문장’(sentence) w가 T*에 속하는 경우 즉, 에서 w는 L(G)의 문장이다. 정의 10.5 정의 10.6

에제10.4 G = ({S}, {a, b}, P, S)에서 예제 10.4 P : S → aSb S → l 일 때 S  aSb  aaSbb  aabb가 되므로 S aabb로 표현한다. G에 의해 생성된 언어의 문장(Sentence): 스트링 aabb 문장형태(sentential form): 넌터미날을 포함하는 aaSbb 위의 문법에서 S  aSb 생성규칙을 반복적으로 적용할 경우 S  aaSbb  aaaSbbb 의 형태가 되므로 일반적으로 S anSbn anbn (S → l 적용) 의 형태가 되므로 G는 anbn의 형태를 가진 스트링들만 유도 예제 10.4

예제10.5 L = {anbn+1 | n≥0}을 생성하는 문법을 만들어 보자. 예제 10.5 S → Ab A → aAb A → l 는 위의 요구를 만족시킬 수 있다. S  Ab  aAbb  aaAbbb  anbn+1 예제 10.5

예제10.6  ={a,b}이고 na(w)와 nb(w)는 각각 스트링 w에서의 a와 b의 개수를 나타낸다고 하자. 그러면 주어진 생성규칙 P : S → SS S → l S → aSb S → bSa 에 대해 L = {w | na(w)= nb(w)}가 성립한다. 즉, L은 aabb, abaabb, bbaa와 같이 a와 b의 개수가 각각 같은 스트링의 집합이 된다. 예제 10.6

정의 10.7 두개의 문법 G1, G2가 똑같은 언어 L을 생성할 때 G1 과 G2는 ‘동치’(equivalent)라고 한다. 예제10.7 G1 : S → aSa G2 : S → aAa A → aAa 여기서 G1과 G2는 각각 똑같은 언어 L = {anbn | n ≥ 0}을 생성한다. 그러므로 문법 G1과 G2는 동치이다. 정의 10.7 예제 10.7

10.7 튜링머신(Turing Machine) 모델 튜링머신의 정의 M =( Q ,  , ,  , q0 , B, F ) Q : 상태들의 유한 집합  : 입력 심볼의 집합으로서 B를 포함하지 않으며  의 부분 집합  : 허용되는 테이프 심볼들의 유한 집합  : 다음 동작 함수(next move function) Q× → Q × ×{L, R} L과 R은 각각 왼쪽과 오른쪽으로의 이동을 의미 q0 : 시작 상태로서 q0 ∈ Q B 는  에 속하는 블랭크(blank) F: 최종 상태의 집합 (F⊆Q) 튜링 테이프 유한제어 입출력 헤드 a1 a2 ai an B [그림 10.8] 기본적인 튜링머신

예제10.8 다음의 <그림 10.9>는 아래의 전이(transition)에 의한 동작의 전과 후의 상황을 나타낸다. (q0 , a) = (q1, d, R) [그림 10.9] 동작의 전과 후의 상황 예제 10.8 상태 q1 상태 q0

정의 10.8 튜링머신 M에 의해 인식되는 L(M)은 M의 테이프 헤드가 가장 왼쪽 셀에 위치하고 q0상태로부터 시작하여 M이 최종 상태에 들어가게 하는  내의 단어들의 집합이다. 즉, L(M) = {w∈ | q0 w├ 1p  2 for some p∈F and 1,  2 ∈} 이 된다. 어떤 튜링머신 M이 언어 L을 인식하게 된다는 것은 튜링머신 의 상태가 최종 상태에 들어가면서 정지하는 경우이다. 즉 입력이 인식될 때에는 다음 동작이 없다. 그러나 그 단어가 인식되지 않을 때에는 튜링머신이 정지하지 않을 수도 있다. 정의 10.8

예제10.9 다음과 같이 정의된 튜링머신을 살펴보자. 예제 10.9 Q = {q0, q1}  = {a, b} 예제10.9 다음과 같이 정의된 튜링머신을 살펴보자. Q = {q0, q1}  = {a, b}  = {a, b, B} F = {q1}  (q0, a) = (q0, b, R)  (q0, b) = (q0, b, R)  (q0 ,B) = (q1, B, L) 예제 10.9

10.8 촘스키 포함 관계(Chomsky Hierarchy) 형식 언어의 선구자 촘스키는 4가지 문법의 패밀리에다 숫자를 붙여서 포함 관계를 나타냄 무제한(Unrestricted) 문법: type 0  RE 문맥민감(Context-sensitive) 문법: type 1  CSL 문맥자유(Context-free) 문법: type 2  CFL 정규 (Regular) 문법 : type3  REG 문법의 숫자가 커질수록 제한도 많아짐. ‘촘스키 포함 관계’ 모든 type i 언어는 type (i - 1) 언어에 속하는 진부분 집합의 관계이다. 형식언어 (formal language) 알파벳으로 만든 유한길이의 단어들 (finite-length words, 즉 character strings) 의 집합이다

Type-0 문법 (unrestricted grammars) 모든 형식문법을 포함한다. 튜링기계 (Turing Machine) 로 인식가능한 모든 언어를 정확히 생성한다. 그 인식가능한 언어란 튜링기계가 멈추는 모든 string 들을 의미 회귀열거가능 언어 (recursively enumerable languages) 튜링기계를 항상 정지시켜서 결정가능한 (decided)  recursive language 와는 다르다는 것을 주목해야 한다. Type-1 문법 (context-sensitive grammars) context-sensitive languages 를 생성한다. 이 문법은 αAβ → αγβ 형태의 규칙을 가진다 A : nonterminal α, β and γ strings : terminals and nonterminals strings α 와 β 는 empty 일 수 있지만 γ 는 nonempty 이어야 한다.

Type-2 문법 (context-free grammars) context-free languages 를 생성 A → γ 의 형태를 가지는 규칙으로 정의 A : nonterminal γ : terminals and nonterminals). 대부분의 프로그래밍 언어 문법의 이론적 기초 Type-3 문법 (regular grammars) regular languages 를 생성 A → aB , A → a 혹은 A → Ba , A → a 왼쪽에 단 하나의 nonterminal 오른쪽에 단 하나의 terminal을 가지거나 단 하나의 nonterminal 이 뒤따르도록 규칙을 제한한다. finite state automaton 으로 결정가능한 모든 언어들 search patterns 과 프로그래밍 언어의 어휘구조를 정의하는데 사용

문법(계속) [정의11] 문법 G=(N, T, P, )에 대하여 이고 일 때 (1) 유형 0 문법은 생성규칙에 대한 제한이 없는 구 구조 문법 (phrase-structure grammar)임 (2) 유형 1 문법은 생성규칙의 형태가 이며, 문맥 의존문법(context-sensitive grammar)이라고도 함 (3) 유형 2 문법은 생성규칙의 형태가 이며, 문맥자유 문법(context-free grammar)이라고도 함 (4) 유형 3 문법은 생성규칙의 형태가 일 때 또는 이거나 또는 이며, 정규문법(regular grammar)이라고도 함

정리 10.2 촘스키 포함 관계 정리 10.2 (1) 정규 언어(REG)는 문맥자유언어(CFL)의 진부분 집합이다. 정리 10.2 촘스키 포함 관계 (1) 정규 언어(REG)는 문맥자유언어(CFL)의 진부분 집합이다. (2) 공스트링이 아닌 문맥자유언어(CFL)은 문맥민감언어(CSL)의 진부분 집합이다. (3) 문맥민감언어 CSL은 r.e(recursively enumerable) 집합의 진부분 집합이다. 정리 10.2

<그림 10.11> 4가지 타입의 오토마타 문 법 언 어 오토마타 Type 0 r. e Turing Machine <그림 10.11> 4가지 타입의 오토마타 문 법 언 어 오토마타 Type 0 r. e Turing Machine (Unrestricted) Language Type 1 CSL Linear Bounded Automata (Context-sensitive) Type 2 CFL Pushdown Automata (Context-free) Type 3 Regular Finite Automata (Regular) Language

[그림 10.12] 촘스키 포함 관계 [그림 10.13] 확장된 촘스키