PowerPoint 프레젠테이션

Transcription

1 Chapter 03 형식언어와유한오토마타

2 01 형식언어 02 형식문법 03 문법표기법 04 유한오토마타

3 형식언어를이해할수있다. 형식문법을이해할수있다. 문법의표기법에대해이해할수있다. 유한오토마타에대해이해할수있다.

4 3.1 형식언어 언어 : 알파벳으로부터생성되는모든문자열들의부분집합 문법 : 언어는문법 (grammar) 에의해서생성되고정의된다. 문법 generation design 언어 인식기 : 언어는인식기에의해인식된다. [ 표 3-2] 언어와인식기 4

5 3.1 형식언어 [ 정의 3-1] 알파벳 (Alphabet) : 언어의문장을이루는기본적인기호 (Symbol) 알파벳이란공집합이아닌기호들의유한집합으로 로표시한다. [ex 3-1] : 1 = { ㄱ, ㄴ, ㄷ, ㄹ,, ㅎ } 2 = {a, b, c,, z} 3 = {0, 1} 알파벳의미를일반프로그래밍언어에서는사용가능한문자나기호들의집합이라고설명한다. C 언어의경우에알파벳은영문소문자, 영문자대문자, 숫자 0~9, 특수문자 +, *, -, _,... 등이다 [ 정의 3-2] 문자열 (String) : 알파벳 에대한문자열은알파벳에서정의된기호들을나열한유한수열 (finite sequence) [ex 3-2] : 알파벳 ={a, b, c} 일때 a, ca, ccba 등이문자열 문자열은언어이론에서는종종문장 (sentence) 이나단어 (word) 와동의어로사용된다. 언어를구성하는각각의알파벳기호들은하나의문자로표시하는데영어의 a, b, c, 을주로사용하고문자열의이름은 u, v, w, 로나타낸다. 예를들어 w = abaaa 는 abaaa 라는값을갖는문자열의이름이 w 임을나타낸 5

6 3.1 형식언어 [ 정의 3-3] 문자열의길이 (Length) : 문자열을이루는기호의개수이며, 어떤문자열 w 의길이는 w 로표시하고, w 의 cardinality [ex 3-3] w 1 = abc w 2 = abab 의문자열에대한길이 w 1 = 3 w 2 = 4 [ex 3-4] : w = v 1 v 2 v 3 v k 일때 w = k [ 정의 3-4] 문자열의접속 (Concatenation) : 두개의문자열을연결하여새로운문자열을만드는연산 문자열 u, v 가각각 u = a 1 a 2 a 3 a n, v = b 1 b 2 b 3 b m 일경우에두문자열의접속은 u v 혹은 uv 로표시하고 uv = a 1 a 2 a 3 a n b 1 b 2 b 3 b m 이다. [ 예제 3-1] 두문자열 u = dog, v = house 가있을때 u v 와 v u u v = doghouse v u = housedog [ 예제 3-2] [ 예제 3-1] 에서 u v 와 v u 를구해보자. 접속연산에대한길이 u v = u + v = dog + house = 8 v u = v + u = house + dog = 8 6

7 3.1 형식언어 [ 정의 3-5] 공문자열 (Empty string) : 문자열의길이가 0 인문자열 으로표기 어떤문자열 u, v 에대하여다음과같은속성을가짐 u = u = u u v = u v Empty string 을 λ 로도표시하며널문자열 (null string) 이라고도한다. 문자열에서의연산중접속연산은 을항등원으로취한다. a n 은 a 가 n 개연결된문자열을표시하며, a 0 은공문자열을나타낸다. 즉, a n =aaa a(a 가 n 개 ) 이고 a 0 = 이된다. w R 은문자열 w 의역 (reverse) 로 w 를이루는요소들의역순으로얻어진다. [ 예제 3-3] : 문자열 w = ccba 에대한 w R 은문자열 w 의역순 w R = abcc 7

8 3.1 형식언어 [ 정의 3-6] 접두사 (Prefix) : 문자열 w = uv 일때 u 를문자열 w 의접두사 진접두사 (Proper prefix) : u 인접두사 접미사 (Suffix) : 문자열 w = uv 일때 v 를문자열 w 의접미사 진접미사 (Proper suffix) : v 인접미사 [ex3-5] : 문자열 w = house 접두사 :, h, ho, hou, hous, house 진접두사 : h, ho, hou, hous, house 접미사 : house, ouse, use, se, e, 진접미사 : house, ouse, use, se, e [ 정의 3-7] * (reflexive transitive closure, Kleene closure) : 공문자열을포함하는알파벳 에대한접속연산에의해만들어질수있는모든문자열들의집합으로 - 스타 ( star, 클리니클로저 ) 라고읽음. + (transitive closure, positive closure) : * 에서공문자열을제외한모든문자열의집합으로 - 대거 ( dagger, 포지티브클로저 ) 라고읽고 + = * - { } 이다. 8

9 3.1 형식언어 [ex3-6] = {0, 1} * = {ε, 0, 1, 00, 01, 10, 11, 000, } [ex3-7] = {a, b, c} + = {0, 1, 00, 01, 10, 11, 000, } * = {ε, a, b, c, aa, bb, cc, ab, ba, ac, ca, bc, cb, aaa, } + = {a, b, c, aa, bb, cc, ab, ba, ac, ca, bc, cb, aaa, } [ 정의 3-8] 언어 L : 알파벳 에대해서 * 의부분집합 유한언어 (finite language) : 언어에속하는문자열의수가유한개일경우 무한언어 (infinite language) : 언어에속하는문자열의수가무한개일경우 [ex3-8] : = {a, b} L 1 = * = {ε, a, b, aa, ab, ba, bb, aaa, } 는무한언어 L 2 = {a, ba, bbb} 는유한언어 L 3 = {aaa, bbb, aba, bba} 는유한언어 L 4 = {a p p 는소수 (prime number)} 는무한언어 L 5 = {a n b n n 1} 는무한언어 9

10 3.1 형식언어 여기서언어는의미 (semantic) 의개념은포함하지않는다는것 언어란단지문자열들의집합이기때문에형식언어이론은문자열집합의속성에관한이론 언어에서의연산 : [ 정의 3-9] 두언어의합집합 두언어 L 과 M 의합집합 (union) L M 은 L 에속하는문자열이거나 M 에속하는문자열 L M = {s s L 혹은 s M} [ex 3-9] [ex 3-8] 에서 L 2 L 3 L 2 L 3 [ 정의 3-10] 두언어의접속 = {a, ba, bbbb, aaa, bbb, aba, bba} 두언어 L 과 M 의접속 (concatenation) LM 은 L 에속하는문자열과 M 에속하는문자열을접속한것으로교환법칙은성립하지않음. LM = {st s L 혹은 t M} [ex 3-10] [ex 3-8] 에서 L 4 L 5 L 4 L 5 = {a p+n b n p 는소수, n 1} 10

11 3.1 형식언어 [ 정의 3-11] L 의거듭제곱 언어 L 의거듭제곱은재귀적으로다음과같이정의한다 L 0 = { } L n = LL n-1 단, n 1 [ex 3-11] L = {a, ba} 라하면 L 3 ={aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa} [ 정의 3-12] 클리니클로저, 포지티브클로저 언어 L 의클리니클로저 L* 는다음과같이정의한다. L * = L 0 L 1 L 2 L n = 또한언어 L 의포지티브클로저 L + 는다음과같이정의한다. L + = L 1 L 2 L n = L = L * - L 0 예 : L = {0, 1} 이라면 i 1 L * 는 을포함하여 0 과 1 로만들어지는모든문자열 L + 는 0 과 1 로만들어지는모든문자열 i i L i 0 11

12 3.2 형식문법 형식문법은크게두가지방법으로정의할수있다. 생성규칙 production rule 만을가지고표현하거나 [ 정의 3-13] 과같이네가지항목으로정의하는것이다 [ 정의 3-13] 문법 G=(V N, V T, P, S) 정의 1. V N : 논터미널기호들의유한집합 2. V T : 터미널기호들의유한집합 V N V T = ф, V N V T = V 터미널기호와논터미널기호를문법기호 (grammar symbol) 라하며보통 V(vocabulary) 로표시 3. P : 생성규칙 (production rule) 의집합으로다음과같다. α β, α V +, β V * α 를왼쪽부분 (left-hand side), β 를오른쪽부분 (right-hand side) 는왼쪽부분에있는기호가오른쪽부분에있는기호로단순히대체 4. S : V N 에속하는기호로서다른논터미널기호들과구별하여시작기호 (start symbol) 12

13 3.2 형식문법 앞으로사용될기호들의일반적인표기법 1) A, B, C 와같은영문자대문자로구성된기호와시작기호를나타내는 S 는논터미널기호이다. 2) < 와 > 로묶어서나타낸기호도논터미널기호이다. 3) a, b, c 와같은영문자소문자로구성된기호와 +, - 와같은연산자기호, 괄호나쉼표와같은구분자, 0, 1, 2 와같은아라비아숫자등은터미널기호이다. 4) X, Y, Z 와같은영문자끝부분의대문자는터미널기호와논터미널기호를나타내는문법기호이다. 5) 영문자끝부분의소문자인 u, v, w, x, y, z 등은터미널기호들로이루어진문자열을나타낸다. 6) α, β, 와같은그리스어소문자는문법기호로구성된문자열을나타낸다. 7) 만약아무런언급이없으면첫번째생성규칙의왼쪽에있는기호가시작기호. 8) 생성규칙의왼쪽부분에같은기호로구성된생성규칙이여러개일때축약해서사용할수있다. 예를들어 2 개의생성규칙 α β1, α β2 가있을때간단히 α β1 β2 로표현한다. 13

14 3.2 형식문법 [ 예제 3-4] 문법에대해몇가지성질알아보기 1 문법 G =({S, A}, {0, 1}, P, S) 생성규칙 P : S 0AS S 0 A S1A A 10 A SS [ 풀이 ] S, A는논터미널기호, 0과 1은터미널기호, S는시작기호생성규칙의개수는 5개 [ 예제 3-4] 문법을축약하면다음과같다. S 0AS 0 A S1A 10 SS. 14

15 3.2 형식문법 [ 예제 3-5] 문법에대해몇가지성질알아보기 2 P : E E + T E - T T T T * F T / F F F (E) id [ 풀이 ] E, T, F는논터미널기호이고 +, -, *, /, (, ), id는터미널기호, E는시작기호이다. 그리고생성규칙의개수는 8개이다. 15

16 3.2 형식문법 정의된문법으로부터어떤언어가생성되는지, 언어가문법에맞는지를알기위해유도를설명한다 : 유도 (derivation) 만약 α β 가존재하고,, δ V * 이면 * α δ β 로표시 즉, 한문자열에서생성규칙을한번적용해서다른문자열로바꾸는것을나타낸다. : 영번이상의유도 (zero or more derivation) * : 한번이상의유도 (one or more derivation) n α 1 α n : α 1, α 2, α 3,,α n 이 V * 에속하고 α 1 α 2 α 3 α n 이존재 α 1 은 α n 을생성 (produce) 혹은유도 (derive) 한다고함 α n 은 α 1 으로감축 (reduce 된다고함. 는생성규칙에서사용되는기호로단일화살표 (single arrow) 라하고, 는유도과정을나타내는기호로이중화살표 (double arrow) 라한다. 16

17 3.2 형식문법 [ 예제 3-6] 유도하기 [ 예제 3-4] 의문법에서문자열 0, 0000, 등이허용되는지유도 [ 풀이 ] 괄호안은적용된생성규칙이다. 1 S 0 (S 0) 문자열 0 은유도에의해생성되므로문법에맞는문장이다. 2 S 0AS (S 0AS) 0SSS (A SS) 00SS (S 0) 000S (S 0) 0000 (S 0) * 이과정은 S 0000 과같이나타낼수도있다. 문자열 0000 은유도에의해생성되므로문법에맞는문장이다. 17

18 3.2 형식문법 3 S 0AS (S 0AS) 0S1AS (A S1A) 001AS (S 0) 00110S (A 10) (S 0) * 이과정은 S 과같이나타낼수도있다. 문자열 은유도에의해생성되므로문법에맞는문장이다 18

19 3.2 형식문법 [ 예제 3-7] 유도하기 2 id + (id * id) 가 [ 예제 3-5] 의문법에의해생성되는문자열인지확인 [ 풀이 ] 괄호안은적용된생성규칙이다. E E + T (E E+T) T + T (E T) F + T (T F) id + T (F id) id + F (T F) id + ( E ) (F ( E )) id + ( T ) (E T) id + ( T * F ) (T T * F) id + ( F * F ) (T F) id + ( id * F ) (F id) id + ( id * id ) (F id) * 이과정은 E id + (id * id) 와같이나타낼수도있다. 문자열 id + (id * id) 는유도에의해생성되므로문법에맞는문장이다. 19

20 3.2 형식문법 [ 정의 3-15] 문장과문장형태 S w 1 w 2 w 3 w n w 와같은유도과정이있을때 S w 이고 w 가 V * 에속하면 w 를문장형태 (sentential form) 라하고, w 가 V T* 에속할경우, w 를문장 (sentence) 이라한다. 즉, 문장형태는터미널기호와논터미널기호들의조합으로구성되고문장은터미널기호들로만구성 우리가프로그램을작성할때사용하는터미널기호로만구성된문장을언어라한다. * [ 예제 3-8] 문장과문장형태구하기 [ 예제 3-6] 의 2 에서이미유도를했는데, 이때문장과문장형태를구해보자 [ 풀이 ] 유도과정중에있는문자열 S, 0AS, 0SSS, 00SS, 000S, 0000 등은문장형태이고, 터미널기호로만구성된 0000 은문장이다. 문장 0000 은시작기호 S 로부터생성된다고한다. 20

21 3.2 형식문법 [ 예제 3-9] 문장과문장형태구하기 [ 예제 3-7] 에서이미유도를했는데, 이때문장과문장형태를구해보자 [ 풀이 ] 유도과정중에있는문자열 E, E + T, T + T, F + T, id + T, id + F, id + (E), id + (T), id + (T * F), id + (F * F), id + (id * F), id + (id * id) 등은문장형태이고, 터미널기호로만구성된 id + (id * id) 는문장이다. 문장 id + (id * id) 는시작기호 E 로부터생성된다고한다. 이렇게문법 G 로부터생성되는문장의집합을언어라하고 L(G) 로표기한다. 문법 G 로부터생성되는언어는시작기호에서유도될수있는모든문장의집합이다 21

22 3.2 형식문법 [ 정의 3-16] 문법 G 에의해생성된언어 L(G) 문법 G에의해생성되는언어는 G에의해생성되는문장의집합이며 L(G) 로표기한다. L(G) = {w S * w, w V T* } [ 예제 3-10] 문법으로부터언어생성하기 1 다음과같은문법으로부터생성되는언어를살펴보자. G1 = ({S, A, B, C}, {a, b}, P, S) P : S A A abc aabc bb bbb bc bb [ 풀이 ] 시작기호로부터생성되는문장은다음과같다. 1 S A (S A) abc (A abc) abb (bc bb) 22

23 3.2 형식문법 2 S A (S A) aabc (A aabc) aabcbc (A abc) aabbbc (bc bb) aabbbbc (bb bbb) aabbbbb (bc bb) 3 S A (S A) aabc (A aabc) aaabcbc (A aabc) aaabcbcbc (A abc) aaabbbcbc (bc bb) aaabbbbcbc (bb bbb) aaabbbbbbc (bc bb) aaabbbbbbbc (bb bbb) aaabbbbbbbb (bc bb) L(G1 ) = {a n b m n, m 1} 23

24 3.2 형식문법 [ 예제 3-11] 문법으로부터언어생성하기 2 다음과같은문법으로부터생성되는언어를살펴보자. G2 = ({S, A}, {b, d}, P, S) P : S dad A dad A b [ 풀이 ] 시작기호로부터생성되는문장은다음과같다. 1 S dad (S dad) dbd (A b) 2 S dad (S dad) ddadd (A dad) ddbdd (A b) 24

25 3.2 형식문법 3 S dad (S dad) ddadd (A dad) dddaddd (A dad) dddbddd (A b) L(G2 ) = {d n bd n n 1} 25

26 3.2 형식문법 앞에서정의한문법의개념은촘스키 (Chomsky, N.) 에의해서처음으로소개되었 고, 그는문법을생성규칙에가해지는제한에따라네종류로나누었으며, 이를 촘스키계층구조라고부른다. 26

27 3.2 형식문법 어떤문법이주어졌을때, 그문법이어디에속하는지판별해보고그언어가생성하는언어를살펴보자 *. 문법을판별하는방법 우선문맥인식문법인지를판별 문맥인식문법이아니라면무제약문법 문맥인식문법이라면문맥자유문법인지판별 문맥자유문법이아니라면문맥인식문법 문맥자유문법이라면정규문법이지판별 정규문법이아니라면문맥자유문법 27

28 3.2 형식문법 [ 예제 3-14] 문법의종류판별하기 1 [ 예제 3-4] 의문법이네가지문법중어디에속하는지판별해보자. S 0AS 0 A S1A 10 SS [ 풀이 ] 우선문맥인식문법인지판별하려면각생성규칙의길이를검사해본다. 모든생성규칙이 α β 에서 α β 를만족하므로문맥인식문법이다. 다음으로문맥자유문법인지는생성규칙의왼쪽부분이논터미널기호하나로구성되어있는지확인하면되는데모두맞으므로문맥자유문법이다. 마지막으로정규문법인지알아보면, 생성규칙 S 0AS 에서생성규칙의오른쪽부분이정규문법에맞지않기때문에정규문법이아니다. 그러므로이문법은문맥자유문법이다. 28

29 3.2 형식문법 [ 예제 3-15] 문법의종류판별하기 2 [ 예제 3-5] 의문법이네가지문법중어디에속하는지판별해보자. E E + T E - T T T T * F T / F F F (E) id [ 풀이 ] 우선문맥인식문법인지알아보면모든생성규칙이 α β 에서 α β 를만족하므로문맥인식문법이다. 그리고생성규칙의왼쪽부분이논터미널기호하나로구성되어있으므로문맥자유문법이다. 하지만생성규칙 E E + T 에서생성규칙의오른쪽부분이정규문법에맞지않기때문에정규문법이아니다. 그러므로이문법은문맥자유문법이다. 29

30 3.2 형식문법 [ 예제 3-16] 문법의종류판별하기 3 [ 예제 3-10] 의문법이네가지문법중어디에속하는지판별해보자. P : S A A abc aabc bb bbb bc bb [ 풀이 ] 우선문맥인식문법인지알아보면모든생성규칙이 α β 에서 α β 를만족하므로문맥인식문법이다. 그리고생성규칙 bb bbb 에서생성규칙의왼쪽부분이논터미널기호하나로이뤄져있지않기때문에문맥자유문법이아니다. 그러므로이문법은문맥인식문법이다 30

31 3.2 형식문법 [ 예제 3-18] 문법의종류판별하기 5 [ 예제 3-12] 의문법이네가지문법중어디에속하는지판별해보자. P : S 0S 0B B 1C C 0C 0 [ 풀이 ] 우선문맥인식문법인지알아보면모든생성규칙이 α β 에서 α β 를만족하므로문맥인식문법이다. 그리고생성규칙의왼쪽부분이논터미널기호하나로구성되어있으므로문맥자유문법이다. 또한생성규칙모두정규문법에맞으며우선형문법이다 31

32 3.2 형식문법 네가지문법의포함관계 32

33 3.2 형식문법 일반적으로형식언어이론에서자주인용되는언어들 1) 단순매칭언어 (simple matching language) : CFL L m = {a n b n n 0} 2) 중복매칭언어 (double matching language) : CSL L dm = {a n b n c n n 0} 3) 좌우대칭언어 (mirror image language) : CFL L mi = {ww R w V T* } 4) 회문언어 (palindrome language) : CFL L r = {w w = w R } 5) 괄호언어 (parenthesis language) : CFL L p = {w w는 balanced parenthesis} 33

34 3.2 형식문법 [ 표 3-2] 언어와인식기 34

35 3.3 문법의표기법 정규표현 (Regular Expression) 문법도표 (Syntax Diagram) BNF EBNF 35

36 3.3 문법의표기법 정규표현 : 정규문법을가장잘표현할수있는방법 [ 정의 3-17] 다음과같이재귀적으로정의 기본단계 알파벳 에대해서 1. Ф,, a V T 는모두정규표현이다. 2. 만일 r, s 가정규언어 L r, L s 를표현하는정규표현이라하면, (1) (r) + (s) 는 L r L s 를나타내는정규표현이다. (2) (r) (s) 는 L r L s 를나타내는정규표현이다. (3) (r) * 는 (L r ) * 를나타내는정규표현이다. 위의정의에서연산자의연산자우선순위 (precedence) 는 * > > + 이며괄호는연산순위때문에사용하였다. 만약연산자 *( 클리니클로저 ) 가우선순위가가장높고왼쪽결합법칙을택하며, 연산자 ( 접속 ) 이두번째우선순위를갖고왼쪽결합법칙을가지며, 연산자 +( 합집합 ) 가가장낮은우선순위를갖고왼쪽결합법칙을갖는다. 만약연산자우선순위와결합법칙이결정되면괄호를사용하지않아도될것이다. 36

37 3.3 문법의표기법 다음정규표현의연산순서는? 37

38 3.3 문법의표기법 [ 예제 3-20] 정규표현에의해생성되는언어 알파벳 Σ = {0, 1} 에대해정규표현이나타내는언어는? (0 + 1)0 3 0* 4 (0 + 1)* [ 풀이 ] 은언어 {0, 1} 을나타낸다. 2 (0 + 1)0 은언어 {00, 10} 을나타낸다. 3 0* 는언어 {ε, 0, 00, 000, } 을나타낸다. 4 (0 + 1)* 는언어 {ε, 0, 1, 00, 01, 10, 11, 000, } 을나타낸다. 즉 ε 을포함하여 0 과 1 로만들수있는모든문자열의집합이다. [ex 3-12] (a + b)*abb 는 a 와 b 로만들어지는모든문자열중에서 abb 로끝나는문자열의집합이다. 38

39 3.3 문법의표기법 [ 예제 3-21] 정규표현인지판단하고생성되는언어구하기 Σ = {0, 1, a, b} 에대해정규표현인지아닌지를판단하고생성되는언어를설명해보자. 1 0 * (0+1) * [ 풀이 ] 1 [ 정의 3-17] 의기본단계 ❸ 번에의해 0 과 1 은정규표현이고, 0 이정규표현이므로귀납단계 ❸ 번에의해 0* 는정규표현이다. 같은방법으로 0 과 1 이정규표현이므로귀납단계 ❶ 번에의해 (0 + 1) 도정규표현이다. (0 + 1) 이정규표현이므로귀납단계 ❸ 번에의해 (0 + 1)* 도정규표현이다. 또한 0* 와 (0 + 1)* 가정규표현이므로귀납단계 ❷ 번에의해 0*(0 + 1)* 도정규표현이다. 이언어는 ε 을포함하여 0 과 1 로만들수있는모든문자열의집합이다. 39

40 3.3 문법의표기법 [ 예제 3-22] 정규표현으로나타내기 다음과같은문법에서 ident 를정규표현으로나타내보자. <ident> ::= (<letter> _){<letter> <digit> _} <letter> ::= a z <digit> ::= [ 풀이 ] (l + _)(l + d +_ ) * 단, l a z d ident 는첫자가영문자소문자 a,, z, 언더바로시작하고두번째자부터는영문자소문자 a,, z, 숫자 0, 1,, 9 그리고언더바가되며길이는제한이없는문자열이다. 40

41 3.3 문법의표기법 [ 정리 3-1] 정규표현의대수학적성질 다음과같은문법에서 ident 를정규표현으로나타내보자. <ident> ::= (<letter> _){<letter> <digit> _} <letter> ::= a z <digit> ::= [ 풀이 ] (l + _)(l + d +_ ) * 단, l a z d ident 는첫자가영문자소문자 a,, z, 언더바로시작하고두번째자부터는영문자소문자 a,, z, 숫자 0, 1,, 9 그리고언더바가되며길이는제한이없는문자열이다. 41

42 3.3 문법의표기법 [ 정리 3-1] 정규표현의대수학적성질 ❶ (α + β) + γ = α + (β + γ) (+ 에대한결합법칙 ) ❷ (αβ)γ = α(βγ) ( 접속에대한결합법칙 ) ❸ α + β = β + α (+ 에대한교환법칙 ) ❹ α + α = α ❺ α(β + γ) = αβ + αγ ( 분배법칙 ) ❻ (β + γ)α = βα + γα ( 분배법칙 ) ❼ εα = α = αε ( 접속연산의항등원 ) ❽ α* = ε + αα* ❾ (α*)* = α* 42

43 3.3 문법의표기법 문법도표 쉽게이해할수있도록문법을도식화하는방법 문법도표는사각형과타원그리고이들사이를연결한간선 (edge) 으로구성 문법도표를그리는방법 1. 터미널기호 b 는원안에 b 로표기하고, 다음기호를보기위해나가는간선을그린다. 2. 논터미널기호 B 는사각형안에 B 를표기하고, 터미널기호의표기법과같이간선을그린다 3. 생성규칙 A X 1 X 2 X n 은다음과같이문법도표로표시한다. X i 가논터미널기호인경우 만약 X i 가터미널기호인경우에는사각형대신에원을사용 43

44 3.3 문법의표기법 4. 생성규칙 A X 1 X 2 X n 은다음과같이문법도표로표시 X i 가논터미널기호인경우 만약 X i 가터미널기호인경우에는사각형대신에원을사용 5. 정규표현 A α * 는다음과같은문법도표로표현 44

45 3.3 문법의표기법 [ 예 3-23] 문법도표로표현하기 다음문법을문법도표로표현하라. G = (V N, V T, P, S) V N = {A, B, C} V T = {a, (, ), b, c} P : A a (B) B bc C {c} S = A 각논터미널기호에대한문법도표를그리면 이문법도표는시작기호에대해한꺼번에표현 45

46 3.3 문법의표기법 BNF(Backus-Naur Form) 표기법 프로그래밍언어의형식적정의 (formal definition) 을위해가장널리사용되는방법 이표기법은 ALGOL 60 의문법을표현하기위해가장먼저사용 현재에는대부분의언어들을표현하는데가장많이사용 이표기법은메타기호 (meta-symbol; 메타기호는표현하려는언어의일부분이아니라, 그언어를표현하려고사용된특수기호 ) 로서세가지기호를사용 논터미널기호는 < 와 > 로묶어표현 대체 (replacement) 를나타내기위해서 ::= 를사용 양자택일을나타내기위해서 를사용 46

47 3.3 문법의표기법 [ 예제 3-24] BNF 로표현하기 1 [ 예제 3-5] 의문법을 BNF 표기법으로표현해보자. 논터미널기호인 E, T, F 는각각 <E>, <T>, <F> 로나타내고, 대체인 는 ::= 로표시하면된다. P : <E> ::= <E> + <T> <E> - <T> <T> <T> ::= <T> * <F> <T> / <F> <F> <F> ::= (<E>) id [ 예제 3-25] BNF 로표현하기 2 첫번째기호가영문소문자로시작하고, 두번째기호부터는영문소문자나숫자이며, 길이에제한이없는식별자를 BNF 표기법으로표현해보자. < 식별자 > ::= < 영문 > < 식별자 >< 영문 > < 식별자 >< 숫자 > < 영문 > ::= a b c z < 숫자 > ::=

48 3.3 문법의표기법 [ 예제 3-25] 에서정의한식별자의길이가길어야 8 이라고하면 BNF 를이용해서표현하기에는다음과같은어려움이따름 < 식별자 > ::= < 영문자 > < 영문자 >< 영문자 > < 영문자 >< 숫자 > < 영문자 >< 영문자 >< 영문자 > < 영문자 >< 영문자 >< 숫자 > < 영문자 >< 숫자 >< 영문자 > < 영문자 >< 숫자 >< 숫자 > < 영문자 >< 숫자 >< 숫자 >< 숫자 >< 숫자 >< 숫자 >< 숫자 >< 숫자 > < 영문자 > ::= a b c z < 숫자 > ::= 위와같이나열해야되는데중간에엄청난가지수의생성규칙이존재 이와같이 BNF는반복되는부분을표시하는데어려움을가짐 반복되는부분을쉽게표시하면서 BNF로표시하는방법이 EBNF이다. 48

49 3.3 문법의표기법 EBNF(Extended BNF) 표기법 반복되는부분을 BNF 표기법보다읽기쉽고간결하게표현 반복되는부분을나타내기위해서메타기호로 { } 와 < > 를사용 {a} 는 a가 0번이상반복될수있다는것을의미 정규표현 a * 와같은의미로생각 또한선택적인부분을표시할때는 [ ] 로표현 [x] 는 x가나타나지않거나한번나타날수있음을의미 [x] 는 {x} 과같은의미 메타기호를 terminal 기호로사용하는경우에는그기호를작은따옴표 (' 와 ) 로묶어표현 { }, [ ],, < >), ::= 와같이 EBNF에서사용되어지는메타기호를터미널기호로사용하는경우발생하는혼돈을피하기위해서사용 49

50 3.3 문법의표기법 [ 예제 3-27] EBNF 로표현하기 1 첫번째기호가영문소문자로시작하고, 두번째기호부터는영문소문자나숫자이며, 최대여덟자인식별자를 EBNF 표기법으로표현해보자. [ 풀이 ] < 식별자 > ::= < 영문자 >{< 영숫자 >} < 영숫자 > ::= < 영문자 > < 숫자 > < 영문자 > ::= a b c z < 숫자 > ::= [ 예제 3-28] EBNF 로표현하기 2 if 문장에서 else 부분이선택적으로나타날수있다면다음과같이표현 7 0 <if_st> ::= if <condition> then <statement> [else <statement>] 50

51 3.3 문법의표기법 [ 예제 3-29] 메타기호를터미널기호로사용하기 메타기호 ::= 과 를터미널기호로사용 <BNF_rule> ::= <left_part>'::='<right_part> <right_part> ::= <right_part_element>{' '<right_part_element>} 51

52 오토마타 디지털컴퓨터의추상적모델 입력자료를읽는기능, 출력기능, 무한개의기억소자 (cell) 로이루어진일시기억장치, 유한개의내부상태중하나의상태를항상유지하는제어 (control) 장치로구성 52

53 기능적인측면에서인식기 (accepter) 와변환기 (transducer) 로구분 인식기의경우입력된결과에대해오토마타는인식 / 기각 (accept/reject) 등을표시하는이진기호를출력 언어변환기는주어진입력에대응하는새로운문자열을출력 변환기에는상태에따른출력을내는 Moore 기계와전이에따른출력을내는 Mealy 기계등이있다. 오토마타는결정적오토마타 (deterministic automata) 와비결정적오토마타 (non-deterministic automata) 로구분 결정적오토마타는한상태에서하나의입력을받았을때다음상태가유일하지만비결정적오토마타는한상태에서하나의입력을받았을때다음상태가두개이상인것을말한다. 53

54 유한오토마타 어떤알파벳 로부터만들어지는문자열의특별한것들을받아들이는시스템의수학적모델로서, 그시스템에서변화할수있는상태가유한개인것. 컴퓨터의여러분야에서널리사용되고있는데특히플립플롭 (flip-flop) 을비롯한여러컴퓨터관련고안물들, 형식언어의연구, 그리고컴파일러등에유용하게쓰임 일반적으로컴파일러중에서어휘분석기는유한오토마타의대표적인것 표현방법 상태전이도 (state transition diagram) 와같이비형식적 (informal) 으로표현하는방법 - 상태전이도는그래프를통하여쉽게개념이들어오기때문에일반적으로유한오토마타를설명할때상태전이도를많이사용 형식적 (formal) 으로표현하는방법 - 5 가지의구성원소들로표현하는방법 상태전이도 오토마타의각상태 (state) 를노드 (node) 로표현 이동함수 (q,a)=p 에대해서는상태 q 에서 p 로가는라벨 (label) 이 a 인간선 (edge) 으로표기 최종상태들은이중원 (double circle) 으로나타내고, 시작상태는시작간선으로표시하는유향그래프 (directed graph) 54

55 [ 예제 3-30] 상태전이도로표현하기 1 [ex 3-12] 의정규표현 (a + b)*abb 를인식하는유한오토마타를상태전이도로표현해보자. [ 풀이 ] [ 예제 3-30] 의유한오토마타가문자열 aabb 를인식할수있는지살펴보자. 시작상태 q0 에서입력 a 를만나면 q0 상태를유지하고, 다음문자인 a 를입력받으면 q1 상태로전이한다. 그리고 q1 상태에서다음입력인 b 를받으면 q2 상태로전이하고, 다시 b 를입력받으면 q3 상태로전이한다. 입력을다읽은후의상태가 q3 이므로문자열 aabb 는주어진유한오토마타에의해인식된다. 하지만문자열 aabb 가이런식으로만되는것은아니다. 55

56 [ 예제 3-31] 상태전이도로표현하기 2 첫번째기호가영문소문자로시작하고, 두번째기호부터는영문소문자나숫자이며, 길이에제한이없는식별자를인식하는유한오토마타를상태전이도로표현해보자 [ 풀이 ] 시작상태인 q0 에서시작하여 a, b,, z 등의영문자가나오면다음상태이자최종상태인 q1 로가서종료될수있으며, 계속해서영문자 a, b,, z 나숫자 1, 2,, 9 등이나오면다시반복할수있다는의미이다. 56

57 [ 정의 3-18] 유한오토마타의형식적정의 유한오토마타를형식적으로표현하면 5-튜플 (tuple) 로구성 유한오토마타를 M 이라하면, M = (Q,,, q 0, F) 단, Q: 상태들의유한집합 : 입력기호들의유한집합 q 0 : 시작상태 (start state, initial state) 로 q 0 Q F : 종결상태들의유한집합 F Q : 전이함수 (transition function) 로서 Q 2 Q (Q의멱집합 ) 즉, (q, a) = {P 1, P 2,, P n } 단, {P 1, P 2,, P n } Q 57

58 [ 예제 3-32] 형식적으로표현하기 1 [ 예제 3-30] 의정규표현 (a + b)*abb 를인식하는유한오토마타를형식적으로표현 [ 풀이 ] 유한오토마타를 M 이라하면, M = (Q, Σ, δ, q0, F) 단, Q = {q0, q1, q2, q3} Σ = {a, b} δ:δ(q0, a) = {q0, q1} δ(q0, b) = {q0} δ(q1, a) = {q2} δ(q2, b) = {q3} q0 = q0 F = {q3} 58

59 [ 예제 3-33] 형식적으로표현하기 2 첫번째기호가영문소문자로시작하고, 두번째기호부터는영문소문자나숫자이며, 길이에제한이없는식별자를인식하는유한오토마타를형식적으로표현 [ 풀이 ] 유한오토마타를 M 이라하면, M = (Q, Σ, δ, q0, F) 단, Q = {q0, q1} Σ = {a, b, c,, z, 0, 1, 2,, 9} δ:δ(q0, a) = {q1} δ(q0, b) = {q1} δ(q0, c) = {q1} δ(q0, d) = {q1} δ(q0, e) = {q1} δ(q0, f) = {q1} δ(q0, g) = {q1} δ(q0, h) = {q1} δ(q0, i) = {q1} δ(q0, j) = {q1} δ(q0, k) = {q1} δ(q0, l) = {q1} δ(q0, m) = {q1} δ(q0, n) = {q1} δ(q0, o) = {q1} δ(q0, p) = {q1} δ(q0, q) = {q1} δ(q0, r) = {q1} δ(q0, s) = {q1} δ(q0, t) = {q1} δ(q0, u) = {q1} δ(q0, v) = {q1} δ(q0, w) = {q1} δ(q0, x) = {q1} δ(q0, y) = {q1} δ(q0, z) = {q1} δ(q1, a) = {q1} δ(q1, b) = {q1} δ(q1, c) = {q1} δ(q1, d) = {q1} δ(q1, e) = {q1} δ(q1, f) = {q1} 59

60 δ(q1, g) = {q1} δ(q1, h) = {q1} δ(q1, i) = {q1} δ(q1, j) = {q1} δ(q1, k) = {q1} δ(q1, l) = {q1} δ(q1, m) = {q1} δ(q1, n) = {q1} δ(q1, o) = {q1} δ(q1, p) = {q1} δ(q1, q) = {q1} δ(q1, r) = {q1} δ(q1, s) = {q1} δ(q1, t) = {q1} δ(q1, u) = {q1} δ(q1, v) = {q1} δ(q1, w) = {q1} δ(q1, x) = {q1} δ(q1, y) = {q1} δ(q1, z) = {q1} δ(q1, 0) = {q1} δ(q1, 1) = {q1} δ(q1, 2) = {q1} δ(q1, 3) = {q1} δ(q1, 4) = {q1} δ(q1, 5) = {q1} δ(q1, 6) = {q1} δ(q1, 7) = {q1} δ(q1, 8) = {q1} δ(q1, 9) = {q1} q0 = q0 F = {q1} [ 예제 3-33] 에서보듯이전이함수는매우길기때문에이를간단하게나타내기위해상태전이표 (state transition table) 를도입한다. 상태전이표는유한오토마타의상태전이를행렬 (matrix) 로나타낸것으로, 행렬의행과열은각각상태집합과입력기호를나타내고행과열이교차하는위치에다음상태를기록한다. 만약전이함수가상태와입력에해당하는위치에값이없다면상태전이표에서그위치에 ø을넣는다. 60

61 [ 예제 3-33] 의전이함수는다음과같이간단하게상태전이표로나타낼수있다. 전이함수는유한오토마타의상태전이를행렬 (matrix) 로표시한상태전이표 (state transition table) 로표시되어진다. 이상태전이함수의형태에따라결정적유한오토마타 (Deterministic Finite Automata; DFA) 와비결정적유한오토마타 (Nondeterministic Finite Automata; NFA) 를구분한다. 61

62 [ 정의 3-19] 결정적유한오토마타 (DFA) DFA 는다음의두가지조건을만족해야한다. 첫째, ε 에의한상태전이 (state transition) 가없고 둘째, δ(q, a) = {P 1, P 2,, P n } 에서 n = 1 이다. 즉, δ : Q x Σ Q 다시말하면, 임의의상태에서하나의입력기호에대해서다음상태는오직하나이거나상태전이가없어야한다. ε 에의한상태전이를 ε- 전이라고도한다. [ 예제 3-34] DFA 확인하기 1 [ 예제 3-33] 의유한오토마타가 DFA 인지알아보자. [ 풀이 ] [ 예제 3-33] 의유한오토마타는 ε 에의한상태전이가없고, 임의의상태에서하나의입력에대해다음상태가단하나이므로 DFA 이다. 62

63 [ 예제 3-36] DFA 확인하고상태전이도로표현하기 0 과 1 이짝수개인문자열을받아들이는다음과같은유한오토마타가 DFA 인지알아보고상태전이도로표현해보자 [ 풀이 ] M = (Q, Σ, δ, q 0, F) 단, Q = {q 0, q 1, q 2, q 3 } Σ = {0, 1} δ 0 1 q 0 q 2 q 1 q 1 q 3 q 0 q 0 = q 0 F = {q 0 } q 2 q 0 q 3 q 3 q 1 q 2 [ 풀이 ] ε 에의한상태전이가없고, 임의의상태에서하나의입력에대해다음상태가단하나이므로 DFA 이다. 이를상태전이도로표현하면다음과같다. 63

64 [ 예제 3-37] DFA 로부터문장인식하기 [ 예제 3-33] 의식별자를인식하는유한오토마타는 DFA 인데이 DFA 로부터문장 a12 를인식해보자. [ 풀이 ] 시작상태가 q0 이므로다음과같은과정을거친다. δ(q0, a) = q1 δ(q1, 1) = q1 δ(q1, 2) = q1 모든입력을읽은후마지막에도달한상태가 q1 이며, 최종상태가 q1 이므로 a12 는주어진 DFA 에의해인식된다. [ 예제 3-39] DFA 로부터문장인식하기 3 [ 예제 3-36] 의 DFA 로부터 0101 을인식하는과정을알아보자. [ 풀이 ] 시작상태가 q0 이므로다음과같은과정을거친다. δ(q0, 0) = q2 δ(q2, 1) = q3 δ(q3, 0) = q1 δ(q1, 1) = q0 모든입력을읽은후마지막에도달한상태가 q0 이며, 최종상태가 q0 이므로 0101 은주어진 DFA 64

65 앞의과정에서주어진 DFA에의해서인식되는문자열이무엇인지를알기가어렵다. 이를위하여전이함수를다음과같이확장해보자. Q Q Q * Q 확장된전이함수는한개의기호를문자열로확장하는것이다. 즉, (q 0, ε) = q 0 (q 0, wa) = ( (q 0, w), a) 와같이확장해야한다. 여기서, w * 이고 a 이다. 즉, q 0 상태에서문자열 wa 를본다는것은 w 를전부본상태에서 a 를보는것과같다는것을의미한다. 65

66 [ 예제 3-40] DFA 로부터문장인식하기 4 [ 예제 3-37] 에서확장된함수에의해문장 a12를인식하는과정을살펴보자. [ 풀이 ] δ*(q0, a12) = δ(δ*(q0, a1), 2) = δ(δ(δ(q0, a), 1), 2) = δ(δ(q1, 1), 2) = δ(q1, 2) = q1 F 그러므로 a12는인식된다. 이는다음과같은방법으로도인식할수있다. δ*(q0, a12) = δ*(q1, 12) = δ(q1, 2) = q1 F. 66

67 [ 정의 3-20] 비결정적유한오토마타 (NFA) 첫째, ε 에의한상태전이가있거나 둘째, δ(q, a) = {P 1, P 2,, P n } 에서 n 2 인 n 이하나라도존재한다. 즉, δ : Q x Σ 2 Q 다시말하면, 어떤상태에서하나의입력기호에대해서다음상태가두개이상인것이하나라도존재한다. [ 예제 3-43] NFA 인지확인하고상태전이도로표현하기 2 개의연속적인 0 이있거나, 2 개의연속적인 1 이있는문자열을받아들이기위한유한오토마타는다음과같다. NFA 인지알아보고형식적으로표현해보자 67

68 [ 풀이 ] 전이함수중 δ(q0, 0) = {q0, q3} 이므로 NFA이다. 이를형식적으로표현하면다음과같다. M = (Q, Σ, δ, q0, F) 단, Q = {q0, q1, q2, q3, q4} Σ = {0, 1} 68

69 q0 = q0 F = {q2, q4} 69

70 [ 예제 3-44] NFA 부터문장인식하기 [ 예제 3-32] 의유한오토마타가문장 baabb 를인식하는지알아보자. [ 풀이 ] 인식하는과정을두가지방법으로풀어볼수있다. 첫번째는하나하나전이함수를적용하여인식하는방법이고, 두번째는갈수있는상태를모두그림으로표현하여인식하는방법이다. 1 δ(q0, b) = {q0} 이된다. (1) δ(q0, a) = {q0, q1} 이된다. (2) 상태가 2 개이므로이중에서현재상태를 q0 으로선택하자. δ(q0, a) = {q0, q1} 이된다. (3) 상태가 2 개이므로이중에서현재상태를 q0 으로선택하자. δ(q0, b) = {q0} 이된다. (4) 다시현재상태 q0 에서입력 b 를읽으면 δ(q0, b) = {q0} 이된다. (5) 입력문자열을다읽은후최종상태는 {q0} 이되었지만최종상태가 {q3} 이므로주어진문자열은인식되지않는다고해야한다. 그러나 NFA 에서는이런결론에문제가있다. 아직도적용하지않은상태가많이남아있기때문이다. 즉 (2) 에서의 q1 상태, (3) 에서의 q1 상태등이다. 이모든상태를적용해야하는데그렇게하려면어떤순서로 70

71 이것또한최종상태에도달하지못한다. 이번에는 (3) 에서 q1 상태부터적용하겠다. δ(q1, b) = {q2} 가된다. δ(q2, b) = {q3} 이된다. 모든입력을읽은후마지막에도달한상태가 {q3} 이고최종상태가 {q3} 이므로문장 baabb 는주어진 NFA 에의해인식된다. 2 이번에는다음과같이그림으로나타내보자. 이경우는시작상태에서출발하여도달가능한모든상태를나타내는것이다. 이중에서입력문자열 baabb 를모두읽은후도달가능한상태는 {q0, q3} 이다. {q0, q3} F = {q3} 문장 baabb 는주어진 NFA 에의해인식된다. 71

72 [ 예제 3-45] NFA 로부터문장인식하기 [ 예제 3-43] 의 NFA 로부터문장 0011 을인식하는지알아보자. [ 풀이 ] [ 예제 3-44] 와같이두가지방법으로풀어보자. 1 δ(q0, 0) = {q0, q3} 이된다. (1) 상태가 2 개이므로이중에서현재상태를 q0 으로선택하자. δ(q0, 0) = {q0, q3} 이된다. (2) 상태가 2 개이므로이중에서현재상태를 q0 으로선택하자. δ(q0, 1) = {q0, q1} 이된다. (3) 상태가 2 개이므로이중에서현재상태를 q0 으로선택하자. δ(q0, 1) = {q0, q1} 이된다. (4) 입력문자열을다읽은후최종상태는 {q0, q1} 이되었다. 그러나최종상태는 {q2, q4} 이므로주어진문자열은인식되지않는다. 72

73 이번에는적용하지않은상태중 (1) 에서 q3 상태부터적용하겠다. δ(q3, 0) = {q4} 가된다. δ(q4, 1) = {q4} 가된다. δ(q4, 1) = {q4} 가된다. 최종상태는 {q2, q4} 이므로문장 0011은주어진 NFA에의해인식된다. 2 이번에는다음과같이그림으로나타내보자. 시작상태에서출발하여입력문자열 0011을모두읽은후도달가능한상태는 {q0, q1, q2, q4} 이다. {q0, q1, q2, q4} F = {q2, q4} 문장 0011은주어진 NFA에의해인식된다. 73

74 [ 예제 3-44], [ 예제 3-45] 에서알수있듯이이런형태로전이함수를적용하면 NFA에의해인식되는문자열이무엇인지명확하게알지못한다. 이를알기위해다음과같이전이함수를하나의입력기호에서입력문자열로확장해보자. δ : Q 2 Q Q * 2 Q 단, δ*(q, ε) = {q} δ*(q, wa) = { δ*(q, w) 에의해서도달할수있는모든상태 p에대해서 δ(p, a)} = δ*(p, a) p ( q, w) 여기서 w * 이고 a 이다. 이것은 q 상태에서 wa 를본다는것은 w 를다본상태들에서 a 를본상태집합의합집합과같다는것을의미 74

75 [ 예제 3-46] NFA로부터문장인식하기 3 [ 예제 3-44] 에서문장 baabb에대해확장된전이함수에적용해보자. [ 풀이 ] δ(q0, baabb) = δ(q0, aabb) = δ(q0, abb) δ(q1, abb) = {δ(q0, bb) δ(q1, bb)} ø = δ(q0, b) δ(q2, b) = {q0} {q3} = {q0, q3} {q0, q3} F = {q3} 문장 baabb는주어진 NFA에의해인식된다. 75

76 NFA 와 DFA DFA 보다 NFA 가언어의구조를쉽게표현 NFA 는 DFA 보다프로그램으로구현하기어려움 DFA 는 NFA 보다프로그램으로구현했을경우에효율면에서훨씬우수 일반적인구현은 DFA 로해야되는데 NFA 가언어의구조를쉽게표현할수있기때문에서로가변환이필요 DFA 와 NFA 는서로가동등 (equivalent) 증명은생략 76

77 NFA 를 DFA 로변환 1. ε- 전이가있는 NFA 를 DFA 로변환 2. ε- 전이가없는 NFA 를 DFA 로변환 ε- 전이가있는 NFA 를 DFA 로변환 이변환은 ε closure 를이용하여변환 NFA 에서의미가같은여러상태들이 DFA 에서하나의상태로변환된다는것 [ 정의 3-21] ε closure 1. S 가한개의상태일경우 ε-closure(s) 는 NFA 의상태 S 와상태 S 로부터레이블이 ε 인간선으로도달될수있는 NFA 의모든상태들의집합 이방법은 ε-closure(s) 의원소가변하지않을때까지반복 2. S 가하나이상의상태집합으로되어있는경우 ε-closure(s) 는 NFA의상태 S안에있는모든상태에대해서 1. 과같은방법으로집합들을구하여합집합한것 ε-closure(s) = ε-closure(x) x s 단, x 는 S 안에포함된상태이다. 77

78 [ 예제 3-48] ε-closure 계산하기 [ 예제 3-30] 의정규표현 (a + b)*abb 를인식하는 NFA 를상태전이도로나타내면다음과같다. 이상태전이도로부터 ε-closure 를구해보자. [ 예제 3-30] 의상태전이도와다른이유와정규표현으로부터 NFA 를만드는방법은뒤에서설명할것이다. 78

79 [ 알고리즘 3-1] 전이가있는 NFA 를 DFA 로변환하는방법 [ 입력 ] 전이가있는 NFA [ 출력 ] 전이가있는 NFA와동등한 DFA [ 방법 ] 1) NFA의시작상태 q 0 에대해 closure(q 0 ) 를구하고 closure(q 0 ) 를 DFA의시작상태로놓는다. 2) DFA의시작상태를집합 D S 에넣는다. 3) 집합 D S 에있는상태에대해서 NFA에있는 를제외한각각의입력기호에대해도달할수있는상태집합을각각 T 1, T 2, 라한다. 그런다음 closure(t 1 ), closure(t 2 ), 를구하여, 이를 DFA의새로운상태로만들어집합 D S 에추가한다. 만약새로운상태들이이미만들어진상태와같은집합이면, DFA의새로운상태로만들지않고현재상태로부터이전에만들어진상태로입력문자에따른간선만만든다. 지금적용한상태를집합 D S 에서제거한다. 4) 집합 D S 가공집합이될때까지과정 3) 을되풀이한다. 5) 만들어진상태중에서 NFA 의최종상태를포함하는상태들은모두 DFA 의최종상태가된다. 79

80 변환에앞서각상태에대해 ε-closure를구한다. ε-closure(0) = {0, 1, 2, 4, 7, 8} ε-closure(1) = {1, 2, 4} ε-closure(3) = {1, 2, 3, 4, 6, 7, 8} ε-closure(5) = {1, 2, 4, 5, 6, 7, 8} ε-closure(9) = {9, 10} ε-closure(11) = {11, 12} ε-closure(0, 9) = ε-closure(0) ε-closure(9) = {0, 1, 2, 4, 7, 8, 9, 10} ε-closure(5, 11) = ε-closure(5) ε-closure(11) = {1, 2, 4, 5, 6, 7, 8, 11, 12} 80

81 [ 예제 3-49] 전이가있는 NFA 를 DFA 로변환하기 [ 예제 3-48] 에 [ 알고리즘 3-1] 을적용하여 ε-전이가있는 NFA를 DFA로변환 [ 풀이 ] 1) ε NFA의시작상태가 0이므로 ε closure(0) 가 DFA의시작상태가된다. ε closure(0) = {0, 1, 2, 4, 7, 8} = A 라하고, D S = {A} 가되고 DFA의시작상태는다음과같다. 2) ε NFA 에있는 ε 를제외한입력기호를보면 a 와 b 이므로 D S 에서 A 를꺼내서각각의입력기호 a, b 에의해도달할수있는상태들을구한다. 각각의상태에대해서 ε closure를구한후, 새로운상태라면이름을붙이면된다. ε closure(3, 9) = {3, 6, 1, 2, 4, 7, 8, 9, 10} = B ε closure(5) = {5, 6, 7, 8, 1, 2, 4}= C D S = {A, B, C} DFA의상태전이도는다음과같다. 81

82 3) D S ={B, C} 가공집합이아니므로알고리즘을되풀이한다. 우선 B 상태에서입력기호 a, b 를보고갈수있는상태집합을구하면 {3, 9}, {5, 11} 이되므로 ε closure{(3, 9)}, ε closure{(5, 11)} 를구한다. ε closure{(3, 9)} = {3, 6, 1, 2, 4, 7, 8, 9, 10} = B ε closure{(5, 11)} = {5, 6, 7, 8, 1, 2, 4, 11, 12} = D 여기에서 ε closure{(3, 9)} 는이미만들어진상태 B 와같으므로새로운상태를만들지않고입력기호에따른간선만그린다. D S ={C, D} 이므로, 같은방법으로 C 상태에서입력기호 a, b 를보고갈수있는상태집합을구하면 {3, 9}, {5} 가되므로 ε closure({3, 9}) 는 B 상태이고 ε closure(5) 는 C 상태이다. 그러므로 DFA 의상태전이도는다음과같다. 82

83 D S ={D} 이다. 4) D S 가공집합이아니므로 D 상태에서입력기호 a, b 를보고갈수있는상태집합을구하면 {3, 9}, {5, 13} 이되므로, ε closure({3, 9}) 는 B 상태이고 ε closure({5, 13}) = {5, 6, 7, 8, 1, 2, 4, 13} = E D S = {E} 이다. 5) D S 가 E 상태에대해서도같은방법으로구하면입력기호 a 에대해 {3, 9}, 입력기호 b 에대해 {5} 를얻으므로 ε closure{3, 9} 는 B 상태이고 ε closure{5} = C 상태가된다. 즉, 83

84 D S 가공집합이므로 ε NFA 의최종상태 13 을포함하는 DFA 의상태를구해보면 E 이므로 E 는 DFA 의최종상태가된다. 즉, 이와같은일련의과정을상태전이표로나타내면다음과같다. 84

85 여기서 A 가시작상태이고 E 가최종상태이다 85

86 [ 정리 3-3] 전이가없는 NFA 를 DFA 로변환하는방법 NFA에의해서인식되는언어를 L이라하면, L을인식하는 DFA가존재한다. L을인식하는 NFA M = (Q,, δ, q 0, F) 라하면, DFA M = (Q,, δ, q 0, F ) 는다음과같이구성 Q = 2 Q 즉, Q 의한상태는 [q 1, q 2,, q ] i 의형태로표시한다. 단, q j Q ( 단, j = 1, 2,, i) 이다. F' = {q Q q는 M의최종상태를포함하는 Q 안에있는모든상태들의집합 } q 0 ' = [q 0 ] δ ({q 1, q 2,, q }, i a) = {P 1, P 2,, P } j 라하면 δ '([q 1, q 2,, q ], i a) = [P 1, P 2,, P ] j 이다. 입력문자열의길이에대하여수학적귀납법으로증명 86

87 [ 예제 3-51] NFA 를 DFA 로변환하기 3 [ 정리 3-3] 을이용하여 ε 전이가없는 NFA를 DFA로변환하시오. NFA M = ({q 0, q 1 }, {0, 1},, q 0, {q 1 }) 단, 이다. 이를상태전이도로나타내면, 87

88 이때 NFA를 DFA로변환해보자. DFA M = (Q, Σ, δ, q0, F ) 라하면 [ 정리 3-3] 에의해다음과같이된다. M = (Q,, δ, q 0, F ) 라하면, Q = {[q 0 ], [q 1 ], [q 0, q 1 ]} q 0 ' = [q 0 ] F' = {[q 1 ], [q 0, q 1 ]} δ : δ ([q 0 ], 0) = δ({q 0 }, 0) = {q 0, q 1 } = [q 0, q 1 ] δ ([q 0 ], 1) = δ ({q 0 }, 1) = {q 0 } = [q 0 ] δ ([q 1 ], 0) = δ ({q 1 }, 0) = f δ ([q 1 ], 1) = δ ({q 1 }, 1) = {q 0, q 1 } = [q 0, q 1 ] δ ([q 0, q 1 ], 0) = δ ({q 0, q 1 }, 0) = {q 0, q 1 } = [q 0, q 1 ] δ ([q 0, q 1 ], 1) = δ ({q 0, q 1 }, 1) = {q 0, q 1 } = [q 0, q 1 ] 이된다. 위의상태전이함수를상태전이표로표시하면다음과같다. 88

89 [q 0 ], [q 1 ], [q 0, q 1 ] 을각각 A, B, C 로상태이름을바꾸고상태전이도를그리면다음과같다. 위의상태전이도는 DFA 로바뀌어져있지만, B 상태는시작상태로부터도달불가능한상태 (inaccessible state) 이므로, 문장을인식하는데불필요한상태가된다. 그러므로 B 상태는제거할수 있으므로다음과같은상태전이도를얻을수있다. 89

90 지금까지두가지방법으로 NFA 를 DFA 로변환하는방법을알아보았다. 이제새로운시도 를해보자. ε- 전이가없는 NFA 를 ε-closure 를이용하여 DFA 로변환하는것이다 [ 예제 3-52] NFA 를 DFA 로변환하기 4 [ 예제 3-51] 에주어진 ε- 전이가없는 NFA 를 DFA 로변환하되 [ 정리 3-3] 을이용하지않고, ε- 전이가있 는 NFA 를 DFA 로변환하는 [ 알고리즘 3-1] 을적용해보자. [ 풀이 ] 1) ε NFA 의시작상태가 q 0 이므로 ε closure(q 0 ) 가 DFA 의시작상태가된다. ε closure(q 0 ) = {q 0 } = A 라하고, D S ={A} 가된다. 2) ε NFA 에있는 ε 를제외한입력기호를보면 0 와 1 이므로 D S 에서 A 를꺼내서각각의입력기호 0, 1 에의해도달할수있는상태들을구한다. 각각의상태에대해서 ε closure 를구한후, 새로운상태라면이름을붙이면된다. A 상태에대해서적용했으므로 D S ={C} 가된다. 3) D S ={C} 가공집합이아니므로알고리즘을되풀이한다. C 상태에서입력기호 0,1 를보고갈수있는상태집합을구하면된다. 90

91 4) D S 가공집합이므로 ε NFA 의최종상태 {q 1 } 을포함하는 DFA 의상태를구해보면 C 이므로 C 는 DFA 의최종상태가된다. 일련의과정을상태전이도로나타내면 ε 전이가없는 NFA 를 DFA 로변환하는방법의결과와같아짐을알수있다. 91

92 DFA 의상태수최소화 (state minimization) DFA를이용하는어휘분석기의상태전이표의크기를줄임 기억공간을적게차지하도록하고또한어휘분석프로그램을간단히하는데큰도움 상태수를최소화하는방법 동치관계 (equivalence relation) 을이용상태수를합침 (state merge) [ 정의 3.22] 구별가능 (distinguishable) 문자열 w * 대해, 만약 q1 상태에서 w를모두본상태가 q3이고 q2에서 w를모두본상태가 q4일때 q3, q4 중하나만종결상태에속하면 2개의상태 q1과 q2는구분가능하다고한다. [ 정의 3.23] 구별불가능 (Indistinguishable) 문자열 w * 에대해, 만약 q1 상태에서 w를모두본상태가 q3이고 q2에서 w를모두본상태가 q4일때 q3, q4가모두종결상태에속하거나모두종결상태가아니라면 2개의상태 q1 과 q2는구분불가능indistinguishable하다고한다 92

93 [ 알고리즘 3-2] DFA 의상태수최소화 (state minimization) [ 입력 ] 하나의 DFA M [ 출력 ] M 과동일한언어를수용하고가능한한적은상태수를갖는하나의 DFA M [ 방법 ] 1) 시작상태로부터도달불가능한상태를모두제거 2) 초기의동치관계인최종상태 (final state) 와최종상태가아닌것 (non-final state) 의두동치류 (equivalence class) 로분할 (partition) 3) 하나의동치류안에서같은입력기호에대해서로다른동치류로가는간선이존재하면또다른분할을하여새로운동치류를만듦 4) 3) 의과정을반복하여더이상새로운분할이일어나지않을때까지반복 5) M 의최종상태에속하는상태가동치류속에있으면이동치류는 M 의최종상태 최소화된 DFA M = (Q,, δ, q 0, F ) 는다음과같은조건을만족 (1) Q' : 동치류의집합으로서 Q' 의한상태를 [q] 로표시 의미는상태 q 를포함하는동치류 (2) [P], [q] 를임의의동치류라하고 δ (P, a) = q 이면 δ' ([P], a) = [q] 이다. (3) q 0 ' = [q 0 ] (4) F' = {[q] q F} 93

94 [ 예제 3-54] DFA 의상태수최소화하기 1 [ 예제 3-49] 에서만들어진다음의 DFA 를최소화해보자. [ 풀이 ] 1. 도달불가능한상태를제거, 그러나도달불가능한상태는존재하지않음 2. 최종상태와최종상태가아닌상태의두동치류 {E} {A, B, C, D} 로만듦 3. 각동치류가각입력기호에대해구별되는가를조사하여더이상분할이일어나지않을때까지반복한다. 94

95 1 번동치류에서입력기호 b 에대해서 {A, B, C} 와 {D} 가구별되므로분할한다. 1 번동치류에서입력기호 b 에대해서 {A, C} 와 {B} 가구별되므로분할한다 95

96 각동치류는더이상구별되지않는다. 마지막으로 DFA 의최종상태가 E 이므로 E 를포함하는모든동치류는 {E} 이므로 {E} 가 M' 의최종상태이다. 그래서각동치류 {A, C}, {B}, {D}, {E} 를 X, Y, Z, W 라하면최소화된 DFA M = (Q,, δ, q 0, F ) 에서 상태수가 5 개에서 4 개로줄었으며최소화된 DFA 를상태전이도로표현하면 96

97 정규언어, 정규문법, 유한오토마타의동치관계 1) 전체문법이주어지면문법으로부터토큰들을분리해내고이토큰들을정규문법으로표현함. 2) 토큰에대한정규문법을정규표현으로표시. 3) 이정규표현을인식하는인식기를만들면을주면언어가주어지면, 이를정규표현으로변환, 4) 정규표현을인식하는 NFA을구성, NFA를 DFA로변환, DFA를최소화하면어휘분석기를만들수있음 정규문법, 정규표현, 유한오토마타의관계가서로동치관계임을증명 1. 정규문법 정규표현 2. 정규표현 유한오토마타 3. 유한오토마타 정규문법 97

98 정규문법 정규표현으로변환 정규표현에의해서정의된문법 G 에의해생성되는언어 L(G) 가무엇인지를알기위해서는, 정규문법을정규표현으로변환 정규문법을계수 (coefficient) 가정규표현으로구성된방정식인정규표현방정식 (regular expression equation) 으로바꾸고정규표현방정식에서해 (solution) 를구함 정규표현방정식으로부터해를구하는방법» [ 정리 3-4] α, β 가정규표현이고, α 가 ε 을포함하지않는다면 X= αx+ β 의유일 한해 (unique solution) 는 X = α * β 이다.» [ 증명 ] 1) 정규표현방정식 X = αx + β 의해가 X = α * β 임을증명 X = α X + β = α(α * β)+ β = α + β + β = (α + + ) β = α * β 이므로 X= αx + β 의해가 α * β 가됨을알수있다. 2) 이해가유일하다는것을증명 => 생략 98

99 [ 알고리즘 3-3] 정규문법 정규표현으로변환알고리즘 [ 입력 ] 정규문법 G = (V N, V T, P, S) 단, V N :non-terminal 기호들의유한집합 V T :terminal 기호들의유한집합 P S : 생성규칙들의집합 A tb, A t 혹은 A Bt, A t 단, t V T * A, B V N : non-terminal 기호로서시작기호 [ 출력 ] 정규문법 G 가생성하는언어 L(G) 를나타내는정규표현 [ 방법 ] (1) 정규문법으로부터정규표현방정식을만든다. (2) 정규표현방정식중 X= αx + β 형태를찾아 X=α * β 로변환한다. (3) 시작기호로부터출발하여다른방정식들을대입한다. 계산결과에 X= αx + β 형태의식이나타나면 X=α * β 로변환하면, 정의된정규문법 G 로부터생성되는정규언어 L(G) 를나타내는정규표현이된다. 99

100 [ 예제 3-56] 정규문법 G = ({S, A, B}, {a, b}, P, S) 가다음과같을때 G로부터생성되는 L(G) 를정규표현으로나타내보자. S aa bs A as bb B ab bb [ 풀이 ] 생성규칙을정규표현방정식으로변환하면 S= aa+bs (1) A=aS +bb (2) B=aB +bb (3) (3) 번식 B=aB +bb+ = (a+b)b + 이므로 X = αx + β형태의식이된다. B = (a+b) * = (a+b) * ---(4) 더이상 X = αx + β 형태가없고시작기호가 S이므로 (1) 번식부터시작 100

101 S=aA + bs =a(as + bb) + bs ( (2) 번식대입 ) =aas + abb +bs =aas + ab(a+b) * +bs ( (4) 번식대입 ) =(aa+b)s + ab(a+b) * 그런데이식은 X = αx + β 형태이므로 S = (aa +b) * ab(a+b) * 101

102 [ 예제 3-57] 정규문법 G = ({S, A, B}, {a, b}, P, S) 가다음과같을때 G로부터생성되는 L(G) 를정규표현으로나타내보자. S aa bs A aa ba b [ 풀이 ] 생성규칙을정규표현방정식으로변환하면다음과같다. S = aa + bs (1) A = aa + ba + b (2) 먼저 (2) 번식에서다음식이유도된다. A = aa + ba + b = (a + b)a + b X = αx + β 형태의식이된다. A = (a + b)*b (3) (1) 번식에 (3) 번식을대입해서풀면다음과같다. 102

103 S = aa + bs = a(a + b)*b + bs = bs + a(a + b)*b 그런데이식은 X = αx + β의형태이므로 S = b*a(a + b)*b이다. L(G) = b*a(a + b)*b 103

104 정규표현 유한오토마타로변환 정규표현의정의에있는각각을받아들이는 ε NFA 를구성 정규표현 ø, ε, a 정규표현 N1+N2, N1 N2, N * 에대해 104

105 [ 예제 3-58] 정규표현을받아들이는유한오토마타만들기 1 정규표현 (a + b)* 를인식하는유한오토마타를구성해보자. 1 a 를인식하는유한오토마타를구성 2 b 를인식하는유한오토마타를구성 3 a + b 를인식하는유한오토마타를구성 4 (a + b)* 를인식하는 유한오토마타를구성 105

106 [ 예제 3-59] 정규표현을받아들이는유한오토마타만들기 2 [ 예제 3-48] 의정규표현 (a + b)*abb 를인식하는 NFA 를구성해보자. 106

107 [ 알고리즘 3-4] 유한오토마타로부터정규문법으로변환 유한오토마타 M = (Q,,, q 0, F) 으로부터정규문법 G = (V N, V T, P, S) 를만드는것은다음과같이하면된다. [ 입력 ] 유한오토마타 M = (Q,,, q 0, F) 단, Q : 상태들의유한집합 : 입력기호들의유한집합 : 상태전이함수 q 0 : 종결기호 [ 출력 ] 정규문법 G = (V N, V T, P, S) 단, V N : non-terminal 기호들의집합 V T : terminal 기호들의집합 P : 생성규칙의집합 S : 시작기호 [ 방법 ] V N = Q V T = S = q 0 P : if (q, a) = r, then q ar; if q F, then q ; 107

108 [ 예제 3-61] 유한오토마타를정규문법으로변환하기 [ 예제 3-60] 의결과인유한오토마타를정규문법 G 로변환해보자. a b start a b A B C b D G = (V N, V T, P, S) 단, V N = {A, B, C, D} V T ={a, b} S = A P : A aa ba ab B bc C bd D 108

109 정규언어, 정규문법, 유한오토마타의동치관계 형식문법 생성기 (talker) = 오토마타 인식기 (listener) 정규문법 정규표현 유한오토마타 109