3. 정규 언어(Regular Language)

Presentation on theme: "3. 정규 언어(Regular Language)"— Presentation transcript:

1 3. 정규 언어(Regular Language)
3-1. 정규 문법과 정규 언어 정규 표현(Regular Expression) 3-3. 유한 오토마타(Finite Automata:FA) 정규 언어의 속성

2 3-1. 정규 문법과 정규 언어 정규 문법의 형태 left-linear grammar(LLG) : nonterminal이 terminal 왼쪽에 나타나는 문법 ABt, At right-linear grammar(RLG) : nonterminal이 terminal 오른쪽에 나타나는 문법 AtB, At  한 문법의 생성규칙이 LLG와 RLG가 혼합이 되어 있으면 정규 문법이 아니다. => context-free grammar(Type 2) <예1> p68|p72 G1 : S  000S | 000 G2 : S  S000 | 000

3 정의 3.1 정규 문법 AaB, Aa, 여기서 aVT이고 A, BVN이다.
정의 3.1 정규 문법 AaB, Aa, 여기서 aVT이고 A, BVN이다. 만약 S이면, S가 다른 생성 규칙의 오른쪽에 나타나지 않아야 한다.(-free 문법) <예 2> 우선형 문법을 정규문법 형태로 변환(p70|74) S  abcA  S  aS1, S1  bS2, S2 cA A  bcA  A  bA1, A1  cA A  cd  A  cA2, A2 d <예 3> L = {anbm | n, m  1}은 정규 언어이다. (p70|74) S  aS | aA A  bA| b

4 정규 문법이 lexical analysis에서 사용되는 이유
Token의 구조는 보통 간단하므로 정규 문법으로도 표현이 가능 context-free 문법보다는 정규 문법으로부터 효율적인 인식기를 쉽게 구현가능 compiler의 front-end를 쉽게 다룰 수 있는 크기의 프로그램으로 나누어 모듈러하게 구성 가능 4

5 3-2. 정규 표현(Regular Expression)
1. 정규표현의 기본요소는 ,, 그리고 terminal 심벌. 는 공집합을 나타내는 정규표현 는 집합 {}를 나타내는 정규표현 aVT는 집합{a}를 나타내는 정규표현 2. 만일 e1과 e2가 정규 언어 L1과 L2를 표현하는 정규표현이라면, (e1)+(e2)는 L1 L2를 나타내는 정규표현(union) (e1) • (e2)는 L1• L2를 나타내는 정규표현(concatenation) (e1)*는 L1* ={} L11  L12  L13 L1n ……를 나타내는 정규표현(closure)

6 정리 3.1 위의 정의된 것 이외에 어떠한 것도 정규 표현이 될 수 없다.
위의 정의된 것 이외에 어떠한 것도 정규 표현이 될 수 없다. 단, (e1) • (e2)의 정규 표현은 편의상 (e1)(e2)로 나타내는 것이 일반적이며, e1+는 e1•e1*의 단축 표현이다. 또한, (e1)+(e2)는 (e1)|(e2)로도 표기된다. <예 4> p72|77, <예 5> p72|77, <예 6> p73|77 정리 3.1 , 가 정규 표현이고, L()이면, X = X + 의 유일한 해는 X= *이다. <예 7> p74|79

7 정규표현의 대수학적 성질(p73|78)  + = + ( +) + =  + ( + )
 + = + ( +) + =  + ( + ) ()  = () (+) =  +  ( + )  =  +    +  =   +  =   =  =   =  =  * = +* * = ( +)* (*)* = * * +  = * * + + = * ( + )* = (**)*

8 정규문법 G가 생성하는 언어 L(G)를 나타내는 정규 표현을 구하는 과정
1. 정규문법으로부터 일련의 정규 표현식을 구성한다 X  |  |  일 때, X =  +  +  로 변환 2. 구성된 정규 표현식 중에 X =X +  형태의 식은 X=*로 푼다. 3. X 대신에 * 를 대입한다. 정규 표현의 공리를 이용하여 X =X + 형태로 정리한 후, 역시 X=*를 적용한다. 이 과정은 시작 심벌에 대한 정규 표현식이 있는 곳으로 계속 진행한다. 4. 시작 심벌에 대한 정규 표현식을 X=X +  형태로 고친 후, 식을 X=*로 풀면 *가 정의된 정규문법으로부터 생성될 수 있는 정규 언어 L(G)가 된다. 문법 G 언어 L(G) 정규표현

9 <예 8> p75~76|80~ <예 9> p76|81
G = ({S, R}, {a, b}, P, S) S aS S  bR S   R  aS 1) S  aS | bR |  2) S = aS + bR +  R = aS 3) S = aS + b(aS) +  = aS + baS +  = (a+ba)S +  = (a+ba)* <예 9> p76|81 G = ({S, A, B}, {a, b}, P, S) S aA | bB | b A  bA |  B  bS 1) S = aA + bB + b A = bA +  = b* B = bS 2) S = ab*+b(bS) + b = ab* + bbS + b = bbS + ab* + b = bbS + (ab* + b) = (bb)*(ab*+b)

10 <추가 예> X1 = 0X2 + 1X1 +  … (1) X2 = 0X3 + 1X2 … (2)
= (01*01*0 + 1)* L(X1) = (01*01*0 + 1)*

11 3-3. 유한 오토마타(Finite Automata:FA)
정의 입력으로 String을 받아 String이 그 언어의 문장이면 “yes” 아니면 “no”라고 답하는 인식기(recognizer) FA M = (Q, , , q0, F) Q : 상태(State)들의 유한 집합  : 입력 심볼의 유한 집합  : 사상 함수(mapping function) or 상태전이 함수 q0: 시작 상태(start 또는 initial state) (q0Q) F : 종결(final state) 상태의 집합을 의미한다. (FQ)

12 q0 q1 q2 a b 예제 : M = ({q0, q1, q2}, {a, b}, , q0, {g2})
<예 11,12,13> (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 이라면 (q0, b) = q2   yes q0 q1 q2  Transition diagram  Transition Table a b

13 정의 3.8 유한 오토마타(DFA) M에 의해 인식되는 스트링 전체를 모아 놓은 집합을 M에 의해 인식되는 언어라고 말하고, L(M)으로 표기한다. L(M) = { x | (q0 , x)  F } <예 3.14> & <예 3.15> P86, 87 13

14 유한오토마타를 상태 전이 함수에 따라 분류 DFA(Deterministic Finite Automata) (결정적 유한 오토마타) FA NFA(Nondeterministic Finite Automata) (비결정적 유한 오토마타)

15 DFA(Deterministic Finite Automata) (결정적 유한 오토마타)
DFA M = (Q,,, q0, F) Q : 상태들의 유한 집합  : 입력 심벌의 유한 집합  : 전이 함수로 Q×Q, 즉 (q, a) = p 이다. q0 : 시작 상태 (q0 Q) F : 종결 상태의 집합을 의미한다(F Q) 특징 한 상태에서 입력 Symbol에 대해 하나의 다음 상태를 갖는다. 에 의한 전이(transition)가 없다.

16 NFA(Nondeterministic Finite Automata) NFA M =(Q,, , q0, F)
(비결정적 유한 오토마타) NFA M =(Q,, , q0, F) Q : 상태들의 유한집합  : 입력 심벌의 유한 집합  : 전이 함수로 Q×2q, 즉 (q, a) = {p1,p2,···,pn} q0 : 시작 상태로 q0Q이며 F : 종결 상태의 집합을 의미하며 FQ이다. 특징 한 상태에서 입력 Symbol에 대해 여러 개의 다음 상태를 가질 수 있다. 에 의한 전이(transition)도 가능

17 NFA(Nondeterministic Finite Automata)
<예 18> p83|89 q2 q1 q3 q0 qf start 0,1 1 

18 NFA에 의해 인식되는 언어를 정의하기 위해 전이함수는 2 단계로 확장 (p89~91)
[단계 1] 입력으로 스트링이 올 수 있도록 확장 (q, ) = {q} (q, xa) =  p (q, x) (q, a) 여기서, x* 이고 a이다. 이것은 q 상태에서 스트링 xa를 본다는 것은 x를 다 본 각각의 상태에서 a를 본 상태들의 합집합과 같다는 것을 의미. <예 19> p90 18

19 ( {p1, p2, …, pk}, x) =  i=1k (pi, x)
[단계 2] 한 개의 상태를 여러 상태로 확장 ( {p1, p2, …, pk}, x) =  i=1k (pi, x) 즉, 일련의 상태에서 스트링 x를 본다는 것은 각각의 상태에서 x를 본 상태들의 합집합과 같다는 것을 의미. <예 20> p90 19

20 정의 3.12 유한 오토마타(NFA) M에 의해 인식되는 스트링 전체를 모아 놓은 집합을 M에 의해 인식되는 언어라고 말하고, L(M)으로 표기한다. L(M) = { x | (q0 , x)  F   } <예 3.21> P91 20

21 정리 3.2 NFA에서 DFA로의 변환(p86|92~ ) NFA M = (Q,, , q0, F)
DFA M´=(Q´,, ´,q0´,F´) Q´ = 2Q (Q의 부분 집합의 집합 : power set) Q´의 한 상태는 [q1, q2, ···, qi]의 형태로 표시한다. q0´ = [q0] F´ = {qQ´ | q는 F의 상태들 중에 적어도 하나를 포함한다.} ({q1, q2, ···, qi}, a) = {p1, p2, ···, pi}이면, ´( [q1, q2, ···,qi] , a) = [p1, p2, ···, pi]이다.

22 A B A C C <예 22> 방법-1 : NFA => DFA(p93~ )
NFA M = ({q0, q1}, {0, 1}, , q0, {q1}) 1) Q´ = {[q0], [q1], [q0,q1]} 2) q0´ = [q0] 3) F´ = {[q1], [q0,q1]} 4) ´ : ´([q0], 0) = ({q0}, 0) = {q0, q1} = [q0, q1] ´([q0], 1) = {q0} = [q0] ´([q1], 0) = ({q1}, 0) =  ´([q1], 1) = ({q1}, 1) = {q0, q1} = [q0, q1] ´([q0, q1], 0) = ({q0, q1}, 0) = {q0, q1} = [q0, q1] ´([q0, q1], 1) = ({q0, q1}, 1) = {q0, q1} = [q0, q1] 1 A B start 1 0,1 1 A C start 0,1 C

23 <예 23> 방법 – 2 : NFA => DFA (p89|95 )
1 2 3 start a,b a b 1. NFA의 시작 상태가 0이므로 DFA의 시작 상태는 [0]이 된다. [0] start 2. 상태[0]에서 a를 보고 갈 수 있는 상태 집합은 {0, 1}이고 [0,1]은 새로운 상태이므로 새로운 상태로 만들어 지시선을 연결한다. [0] [0, 1] start a 상태[0]에서 b를 보고 갈 수 있는 상태 집합은 {0}이고, [0]은 기존의 상태와 같으므로 지시선만 그린다. [0] start [0, 1] a b

24 3. 상태[0, 1]에서 a를 보고 갈 수 있는 상태 집합은 {0, 1}이므로 지시선만
그린다 a b [0, 1] [0] a start 상태[0, 1]에서 b를 보고 갈 수 있는 상태 집합은 {0, 2}이고, [0, 2]는 새로운 상태이므로 다음과 같이 추가하고 지시선을 연결한다. a b [0, 1] [0, 2] [0] a b start 4. 상태 [ 0, 2]에서 a를 보고 갈 수 있는 상태 집합은 {0, 1}이므로 지시선만 그린다. a b b [0, 1] [0, 2] [0] a start a

25 상태 [0, 2]에서 b를 보고 갈 수 있는 상태 집합은 {0, 3}이고, [0, 3]은
새로운 상태이므로 다음과 같이 추가하고 지시선을 연결한다. [0] start [0, 1] a b [0, 2] [0, 3] 상태 [0, 3]에서 a 를 보고 갈 수 있는 상태 집합은 {0, 1}이고, b를 보고 갈 수 있는 상태는 {0}이므로 새로 만들지 않고 지시선만 만든다. [0] start [0, 1] a b [0, 2] [0, 3]

26 6. 더 이상 새로운 상태가 추가되지 않으며, NFA의 종결 상태 3을 포함하는
상태 [0, 3]은 DFA의 종결 상태로 표시한다. [0] start [0, 1] a b [0, 2] [0, 3]  상태 전이표 표현

27 <예제 24> 방법-3 : (예 18)의 NEA를 DFA로 변환(p97)
NFA M = ({q0, q1, q2, q3, qf}, {0, 1}, , q0, {qf}) 1) 우선 NFA 중 여러 상태가 나타나는 것을 고르면, {q1, q2}와 {q1, q3}를 고를 수 있다. 나오는 집합의 원소의 입력 심벌별로 모두 합집합을 취한다. 2) 합집합을 구한 상태에서 새로운 상태가 있으므로 나오는 집합 원소의 입력 심벌별로 모두 합집합을 취한다.

28 B D A 1 C E 3) 처음 종결자를 원소로 갖는 상태는 모두 종결자가 된다.
3) 처음 종결자를 원소로 갖는 상태는 모두 종결자가 된다. 4) 시작 상태에서 도달할 수 없는 상태는 제거한다. B D [q1,q2,qf] [q1,q2] A [q0] 1 1 1 [q1,q3,qf] [q1,q3] 1 1 C E

29 -NFA => DFA로 바꾸는 방법(p92|97~ ) <정의 3.13> -closure
-closure(S) : S와 S로부터 레이블이 으로 쓰인 지시선으로 도달할 수 있는 모든 상태 포함 T가 하나 이상의 상태집합 -closure(T) : -closure(q) < 예제 25> (p92|98) qT a b a  a  A B C D  - closure(A) = {A, B, D} - closure(T) = - closure({A, C}) = - closure(A)  - closure(C) = {A, B, D}  {C, D} = {A, B, C, D}

30 <예제 26> (p93|99) -NFA => DFA
b 1 4 c 3   d a b c e - closure(1) ={1, 3, 4}≡[1,3,4] -closure(2) ={2} ≡ [2] f -closure(3) ={3, 4}≡[3,4] closure(2) -closure(4) = {4} ≡[4] closure(3) ={3, 4}≡ [3,4] closure(4) = {4} ≡ [4] A B C D

31 DFA의 상태 수 최소화 (p95|100~) 초기의 동치관계
A B D [4] [1,3,4] [2] [3,4] a b c C DFA의 상태 수 최소화 (p95|100~) 초기의 동치관계 종결상태, 미종결 상태로 구분 같은 입력에 대해 서로 다른 동치로 가는 지시선이 존재하면, 또 분할 하여 새로운 동치류 구성 2번 과정 반복, 더 분할되지 않으면 새로운 DFA M´ 형성 DFA M´=(Q´,, ´, q0´, F´)

32 <예제 27> p96~97|102~103 a A E C D B a b 1. 1 : {A, B, D} 2 : {C, E} 1 2 3 a,b a b 2. X Y Z X Y Z

33 <예제 27> 계속 3. 더 이상 분할되지 않으므로 X=[A], Y=[B,D], Z=[C,E]로 놓고 DFA M’ 구성 M’ = ( {X, Y, Z}, {a, b}, δ' , X, {Z} ) δ' a b X Y Z 1 2 3 a,b a b X Y Z

34 축약된 오토마타 변환하는 방법(p97|103) 연습 3.11(1), (2) (p126)
어떤 상태로 들어오는 지시선 없이 나가는 지시선만 갖는 도달 불가능한 상태(inaccessible state)는 모두 제거한다. 동치 관계를 이용하여 구별되지 않는 상태들을 하나로 합친 후 새로운 유한 오토마타를 구성한다. 연습 3.11(1), (2) (p126)

35 3-4. 정규 언어의 속성 정규 문법, 정규 표현, 유한 오토마타의 관계 3.4.1 3.2 3.4.2 정규 문법 유한 오토마타
정규 문법, 정규 표현, 유한 오토마타의 관계 정규 문법 3.4.1 3.2 유한 오토마타 정규 표현 3.4.2

36 3.4.1 정규 문법과 유한 오토마타 RG FA (1) (2) (1) RG : G(VN, VT, P, S) => M (Q,, , q0, F) Q : VN  {f}, f : 새로 만들어진 종결상태  : VT q0 : S ; F : if  L(G) then {f} else {S, f}  : if A  aB  P, (A,a) = B; if A  a  P, (A, a) = f ※  함수의 개수는 정규문법의 생성규칙의 개수와 같다. 즉, |  | = | P |

37 <예제 29> (p101|107) : 정규 문법과 동등한 FA 구성
G = ({S,B}, {0, 1}, P, S) P : S  0S S  1B S  S 1 B  0S B  0 => M : (Q, , , q0, F) Q : VN  {f} = {S, B, F}  : VT = {0, 1} q0 : S F : {f}

38 M = (Q,, , q0, F)  G = (VN, VT, P, S)
(2) 유한 오토마타 FA  정규문법 RG M = (Q,, , q0, F)  G = (VN, VT, P, S) VN : Q; VT : ; S : q0; P : if (q, a) = r then q ar; if q F then q;  <예 30> P102|108 DFA  정규 문법 p q r 1 1,0 G = (VN, VT, P, S) VN : Q = {p, q, r} VT :  = {0, 1} S : q0 = p P : p 0q, p  1p q  0r, q  1p r 0r, r  1r, r    정규문법 ※ 생성규칙의 개수는 전이함수의 개수 + 종결상태의 개수, 즉 | P | = |  | + | F |

39 3.4.2 유한 오토마타와 정규 표현(p109~) (1) FA => 정규 표현
(b) 구한 정규 문법으로부터 정규 표현을 얻는다. 유한 오토마타로부터 정규표현을 얻는과정(계속) 1. 오토마타에서 상태 전이표를 구한다. 2. 상태 전이표로부터 정규문법으로 변환한다 (1) (2) 정규 문법 (a) (b) 정규 표현 FA

40 유한 오토마타로부터 정규표현을 얻는 과정 (계속)
3. 정규문법을 정규표현식으로 쓴다. P = p (1) q = 0r + 1p (2) r = 0r + 1r +  (3) 4. 정규 표현식을 풀어서 정규 표현으로 나타낸다. r = 0r + 1r +  = (0+1)r +  = (0+1)* q = 0r + 1p = 0(0+1)* + 1p p = 0q + 1p = 0(0(0+1)* + 1p) + 1p = 00(0+1)* + 01p + 1p = (01 + 1)p + 00(0+1)* = (01+1)*00(0+1)*   L(M) = (01+1)*00(0+1)*

41 (2) 정규표현 => 유한 오토마타(p104|111~ )
정규 표현의 정의로부터 NFA(-NFA) 구성 간단화 방법 적용 => 크기를 줄임 (c) -NFA를 DFA로 변환

42 (a) 정규표현의 정의로부터 -NFA 구성 방법
정규표현 N1+N2, N1•N2, N*에 대해 N1 + N2   : i f i a f a :  N2 N1  N1+N2 : i f  

43 <예 31> 위의 방법에 의해 정규 표현 (a + b)*를 인식하는 FA 구성 p105~106|112~113 
N1•N2 N*  N1•N2 : N1 N2 f    i N f N* :  <예 31> 위의 방법에 의해 정규 표현 (a + b)*를 인식하는 FA 구성 p105~106|112~113   a    start   b 

44 (b) -NFA를 간단화 (p106|113 ~ ) A에서 나가는 다른 지시선이 없을 때 A, B는 같은 상태로 취급될 수 있다. 다음과 같은 형태도 하나의 상태로 줄일 수 있다.  A B : A, B는 같은 상태 a  a A B C A C  a a A B  A 

45 두 개의 경로가 같은 곳으로 이동하는 다음의 경우도 간단화
할 수 있다. a*를 인식하는 경우 다음과 같이 간단히 나타낼 수 있다. a  A B  a,b S F S F  C D   b a a   A B C  A 

46 < 예제 33> (p109|115) (ab)*(ba)*:
2 a b (ab)* : 3 4 (ba)* : 따라서, (ab)*(ba)*를 인식하는-NFA 1 2 3 4 a b 

47 (c) -NFA를 DFA로 변환 상태 전이표를 이용하여 바꾸면 상태 전이도로 표현하면 a A B start a b b C