3. 정규 언어(Regular Language)

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

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

2 3-1. 정규 문법과 정규 언어 정규 문법의 형태 left-linear grammar(LLG) :
nonterminal이 terminal 왼쪽에 나타나는 문법 right-linear grammar(RLG) : nonterminal이 terminal 오른쪽에 나타나는 문법 한 문법의 생성규칙이 LLG와 RLG가 혼합이 되어있으면 정규 문법이 아니다. => context-free grammar

3 정규 문법이 lexical analysis에서 사용되는 이유
정의 3.1 AaB, Aa, 여기서 aVT이고 A, BVN이다. 만약 S이면, S가 다른 생성 규칙의 오른쪽에 나타나지 않아야 한다. 정규 문법이 lexical analysis에서 사용되는 이유 Token의 구조는 보통 간단하므로 표현이 가능 context-free문법보다는 정규 문법으로부터 효율적인 인식기를 쉽게 구현가능 compiler의 front-end를 쉽게 다룰 수 있는 크기의 프로그램으로 나누어 모듈러 하게 구성 가능

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

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

6 정규표현의 대수적 성질 + = + (+)+ = +(+ )
+ = + (+)+ = +(+ ) ()  = () (+) =  +  ( + )  =  +   +  =   +  =   =  =   =  =  * = +* * = (+)* (*)* = * * +  = * *++ = * (+)* = (* *)*

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

8  예제2 G = ({S, R}, {a, b}, P, S) G = ({S, A, B}, {a, b}, P, S) S aS
 예제1 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)*  예제2 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)

9  예제3 X1 = 0X2 + 1X1 +  X2 = 0X3 + 1X2 X3 = 0X1 + 1X3 1) X3 = 1X3 + 0X1 = 1*0X1 2) X2 = 0(1*0X1) + 1X2 = 1X2 + 01*0X1 = 1*01*0X1 3) X1 = 0(1*01*0X1) + 1X1 +  = 01*01*0X1 + 1X1 = (01*01*0 + 1)X1 +  = (01*01*0 + 1)* L(X1) = (01*01*0 + 1)*

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

11 a q0 q1 b b a b a q2  예제  Transition diagram  Transition Table
M = ({q0, q1, q2}, {a, b}, , q0, {g2}) (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  Transition diagram a q0 q1 b b a b a q2  Transition Table

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

13 NFA(Nondeterministic Finite Automata) NFA M =(Q,, , q0, F)
: 입력 심벌의 유한 집합 : 전이 함수로 Q×2q, 즉 (q, a) = {p1,p2,···,pn} q0: 시작 상태로 q0Q이며 F: 종결 상태의 집합을 의미하며 FQ이다.  예제 q2 q1 q3 q0 qf start 0,1 1

14 NFA에서 DFA로의 변환 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]이다.

15 A C B  예제 21 1 start 0,1 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 C B 0,1 start

16  예제 22 1 2 3 1. NFA의 시작상태가 0이므로 DFA의 시작상태는 [0]이 된다. start a,b a b [0] 2. 상태[0]에서 a를 보고 갈 수 있는 상태 집합은 {0, 1}이고 [0,1]은 새로운 상태이므로 새로운 상태로 만들어 지시선을 연결한다. [0] [0, 1] 상태[0]에서 b를 보고 갈수 있는 상태 집합은 {0}이고, [0]은 기존의 상태와 같으므로 지시선만 그린다. start a b

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

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

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

20 예제 17 NFA M = ({q0, q1, q2, q3, qf}, {0, 1}, , q0, {qf}) 1) 우선 NFA중 여러 상태가 나타나는 것을 고르면, {q1, q2}와 {q1, q3}를 고를 수 있다. 나오는 집합의 원소의 입력심벌별로 모두 합집합을 취한다. 2) 합집합을 구한 상태에서 새로운 상태가 있으므로 나오는 집합의 원소의 입력심벌별로 모두 합집합을 취한다.

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

22 A B C D -NFA => DFA -closure a  closure(A) = {A, B, D}
-closure(S) : S와 S로부터 레이블이 쓰인 지시선으로 도달 할 수 있는 모든 상태 포함 S가 하나이상의 상태 -closure(T) : -closure(q)  예제 21 qT A B C D a  closure(A) = {A, B, D} closure(T) = closure({A, C}) = closure(A)  closure(C) = {A, B, D}  {C, D} = {A, B, C, D}

23  예제 2 a b 1 4 c  3 

24 DNF의 상태 수 최소화 4 1,3,4 2 3,4 a b c 초기의 동치관계
종결상태, 미 종결상태로 구분 같은 입력에 대해서 서로 다른 동치로 가는 지시선이 존재하면, 또 분할 하여 새로운 동치류 구성 새로운 M´ 형성

25  예제 A E C D B a b 1. 1 : {A, B, D} 2 : {C, E} 2. 1 2 3 a,b a b

26 오토마타 변환하는 방법 어떤 상태로 들어오는 지시선 없이 나가는 지시선만 갖는 도달
불가능한 상태(inaccessible state)는 모두 제거한다. 동치 관계를 이용하여 구별되지 않는 상태들을 하나로 합친 후 새로운 유한 오토마타를 구성한다.

27 3-4. 정규 언어의 속성 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 (A,a) = B; if A  a (A, a) = f

28  예제 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}

29 M = (Q,, , q0, F) => G = (VN, VT, P, S)
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;  예제 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 q r 1 1,0  정규문법

30 유한 오토마타와 정규 표현 유한 오토마타로부터 정규표현을 얻는 과정 유한 오토마타로 부터 정규문법을 구한다
구한 정규 문법으로부터 정규 표현을 얻는다. 유한 오토마타로부터 정규표현을 얻는 과정 오토마타에서 상태 전이표를 구한다. 상태 전이표로부터 정규문법으로 변환한다 정규문법을 정규식으로 쓴다. P = p (1) q = 0r + 1p (2) r = 0r + 1r +  (3) 정규표현식을 풀어서 정규 표현으로 나타낸다. 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)*

31   : 정규표현 => 유한 오토마타 i f a a : i f N2 N1  정규 표현 , a에 대해,
정규표현 N1+N2, N1•N2, N*에 대해 N1 + N2 i f   : a a : i f N2 N1  N1+N2 :

32 N1•N2 N* N2 N1 f N1•N2 :  N i f  N* :   예제 start  a b

33 -NFA를 간단화 A B  a C  A B a  
예 다음과 같은 형태도 하나의 상태로 줄일 수 있다. A B  a C  A B a  

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

35 1 2 a b (ab)* : 3 4 (ba)* : 1 2 3 4 a b  예제 (ab)*(ba)*:
따라서, (ab)*(ba)*인식하는-NFA 1 2 3 4 a b 

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