푸시다운 오토마타.

Presentation on theme: "푸시다운 오토마타."— Presentation transcript:

1 푸시다운 오토마타

2 문맥 자유 문법 문맥 자유 문법  문맥 자유 언어 유한 오토마타로 인식 불가능 L={anbn : n>= 0}
유한 오토마타 : 유한 메모리 문맥 자유 언어 : 무한한 양의 정보 저장 능력 필요 L={anbn : n>= 0} 모든 a는 b 앞에 놓여야 함 a의 개수 계산이 가능 하여야 함

3 문맥 자유 문법 L={wwR} 해결책 심볼들의 순서열을 역순으로 저장하는 능력 필요 스택과 같은 작동 능력 필요
무한정의 저장 용량 허용

4 푸시다운 오토마타 Input file Stack Control unit

5 푸시다운 오토마타 푸시다운 오토마타 비결정적 문맥-자유 언어 결정적 문맥-자유 언어 결정적  비결정적

6 비결정적 푸시다운 오토마타

7 정의 7.1 비결정적 푸시 다운 인식기는 7개의 요소로 구성 M = ( Q, , , , q0, z, F)
 : 입력 알파벳  : 스택 알파벳  : 전이 함수 Q  (  {})    Q  * q0Q : 제어 유닛의 초기 상태(start state) z : 스택의 시작 심벌 FQ : 종료 상태(final state)의 집합

8 정의 7.1  : 전이 함수 Q  (  {})   제어 유닛의 현재 상태(Q) 읽혀질 심볼(),  전이 가능
스택의 톱에 놓여 있는 심볼()  Q  * 제어 유닛의 다음 상태 (Q) 스택의 톱에 놓여질 심볼 ()

9 예제 7.1 npda가 다음 전이를 포함 (q1,a,b) = {(q2,cd),(q3,)} 현재 상태 가능한 전이
문자열 cd가 스택의 톱에 있는 b를 교체 (q3,) 제어 유닛의 상태 : q3 스택의 톱에 심볼 b는 제거

10 예제 7.2 다음과 같은 npda를 고려 Q={q0,q1,q2,q3}, ={a,b}, ={0,1}, z=0, F={q3}
그리고 (q0,a,0)={(q1,10),(q3, )} (q0,,0)={(q3, )} (q1,a,1)={(q1, 11)} (q1,b,1)={(q2, )} (q2,b,1)={(q2, )} (q2,,0)={(q3, )}

11 예제 7.2 전이 고려 L={anbn : n>= 0}U{a}인식
모든 가능한 입력 심볼과 스택 심볼의 조합에 대해서 규정되지 않음 => 공집합 간주 a가 읽혀지면 스택에 1을 하나 추가 (q1,a,1)={(q1, 11)} b가 읽혀지면 1을 하나 제거 (q1,b,1)={(q2, )}, (q2,b,1)={(q2, )} L={anbn : n>= 0}U{a}인식

12 순간적 묘사 문자열을 처리하는 동안 npda의 연속적인 형상들을 설명하는 표기법 (q,w,u)
u : 스택의 내용(u의 가장 왼쪽 심볼이 스택의 탑) 한 순간적 묘사로부터 다른 순간적 묘사로의 이동은 심볼 로 표기 (q2,y)  (q1,a,b)일때 (q1,aw,bx) (q2,w,yx)

13 PDA에 의하여 승인되는 언어 정의 7.2 M = ( Q, , , , q0, z, F)를 비결정적 푸시다운 오토마타라 하자. M에 의하여 인식되는 언어는 집합 L(M)={w*:(q0,w,z) (p,,u),pF,u*} 즉, M에 의하여 인식되는 언어는 M이 입력심볼을 다 읽고 종료 상태에 놓일 수 있는 문자열의 집합이다. 스택의 내용 u는 인식과는 무관 * M

14 예제 7.3 언어 L={w{a,b}*:na(w)=nb(w)} 에 대한 npda를 구성 a와 b의 순서는 고려할 필요 없음

15 예제 7.3 Npda M=({q0,qf},{a,b},{0,1,z},,q0,z,{qf}) (q0,,z)={(qf,z)}
(q0,a,z)={(q0,0z)} (q0,b,z)={(q0,1z)} (q0,a,0)={(q0,00)} (q0,b,0)={(q0, )} (q0,a,1)={(q0,)} (q0,b,1)={(q0,11)}

16 예제 7.3 문자열 baab 의 유도과정 (q0,baab,z) (q0,aab,1z) (q0,ab,z)
(q0,b,0z) (q0,,z) (qf,,z)

17 예제 7.4 언어 L={wwR:w {a,b)+} 에 대한 npda를 구성
스택을 이용하여 입력 심볼의 삽입된 역순으로 회수될 수 있음을 이용 문자열의 첫 부분을 읽을때 연속적인 심볼들을 스택에 삽입 두번째 부분에서 현재 입력 심볼을 스택의 탑 십볼과 비교하여 두 심볼이 일치하면 처리 계속 수행

18 예제 7.4 npda M=({q0,q1,q2},{a,b},{a,b,z},,q0,z,{q2})
(q0,a,z)={(q0,az)} (q0,b,z)={(q0,bz)} (q0,a,a)={(q0,aa)} (q0,b,a)={(q0,ba)} (q0,a,b)={(q0,ab)} (q0,b,b)={(q0,bb)} 문자열의 중간을 추측하는 전이는 상태를 q0에서 q1 (q0,,a)={(q1,a)} (q0,,b)={(q1,b)}

19 예제 7.4 wR과 스택의 내용이 일치하는지를 확인하는 전이들 (q1,a,a)={(q1, )}
(q1,b,b)={(q1,)} 마지막으로 성공적인 일치를 인식하는 전이 (q1,,z)={(q2,z)}

20 예제 7.4 abba를 승인하는 일련의 이동 (q0,abba,z) (q0,baa,az) (q0,ba,baz)
(q1,ba,baz) (q1,a,az) (a1,,z) (q2,z) 문자열의 중간의 위치 결정을 위한 전이 순간적 묘사(q0,ba,baz)는 두가지 선택 (q0,b,b)={(q0,bb)}를 이용 (q0,ba,baz) (q0,a,bbaz) (q0,,b)={(q1,b)}를 이용 (q0,ba,baz) (q1,ba,baz)

21 푸시다운 오토마타와 문맥-자유 언어 문맥-자유언어 npda

22 문맥-자유 언어에 대한 NPDA 문맥-자유 언어 그 언어를 인식하는 npda가 존재함을 보임 문자열 유도과정
언어가 Greibach 정규형인 문법에 의하여 생성된다고 가정 언어에 속한 모든 문자열의 좌측우선 유도이용 문자열 유도과정 문장형태의 오른쪽 부분에 있는 변수들을 스택에 유지 단말로 이루어진 왼쪽 부분은 읽은 입력과 일치시킴

23 문맥-자유 언어에 대한 NPDA 스택에 시작심볼 입력 생성규칙 A->ax 스택의 탑에 변수 A가 있어야 함

24 예제 7.5 다음 생성규칙을 갖는 문법으로 생성된 언어를 인식하는 pda를 구성 S->aSbb|a

25 예제 7.5 S->aSbb|a 문법을 Greibach 정규형으로 S->aSA|a A->bB B->b
오토마타의 상태 {q0, q1, q2} q0 : 초기상태, q2 : 종료상태 시작심볼 : S 시작 심볼을 위한 전이 정의 (q0,,z)={(q1,Sz)} S->aSbb|a

26 예제 7.5 S->aSA 입력으로 a를 읽는 동안, 스택에서 S를 제거하고 SA로 교체 S->a
=> (q1,a,S)={(q1,SA),(q1,)}

27 예제 7.5 A->bB, B->b (q1,b,A)={(q1,B)} (q1,b,B)={(q1,)}
스택의 시작심볼이 스택의 탑에 나타나면 유도의 완료를 뜻하고 pda는 다음 전이에 의하여 종료 상태에 놓임 (q1,,z)={(q2,)}

28 정리 7.1 모든 문맥-자유 언어 L에 대하여, L=L(M)인 npda M이 존재한다.

29 정리 7.1 언어 L이 -자유인 문맥-자유 언어라면, L에 대한 Greibach 정규형인 문맥-자유 문법이 존재 => G=(V,T,S,P) 문법의 좌측우선 유도를 시뮬레이션 하는 npda 구성 가능 M=({q0,q1,qf},T,VU{z},,q0,{qf}) 입력 알파벳은 G의 단말들의 집합과 동일 스택 알파벳은 문법의 변수들의 집합 포함

30 정리 7.1 전이함수 M의 첫번째 이동 후 스택이 시작심볼 S (q0,,z)={(q1,Sz)}
P에 속한 각 생성규칙 A->au (q1,u)  (q1,a,A) M은 입력 a를 읽고 변수 A를 스택에서 u로 교체 마지막 종료상태를 위해 (q1,,z)={(qf,z)}

31 정리 7.1 * M이 모든 w  L(G)를 승인하는 것을 보이기 위해, 좌측우선 유도를 다음과 같이 보일 수 있다
S => w 이면 (q1,w,Sz) (q1,,z) 이고, (q0,w,z) (q1,w,Sz) (q1,,z) (qf,,z) 따라서 L(G)  L(M)이다. *

32 정리 7.1 만약   L이면, npda에서 빈 문자열이 승인되도록 전이 를 추가하면 된다.
(q0,,z)={(qf,z)} 를 추가하면 된다.

33 예제 7.6 다음의 문법을 고려해보자 S->aA A->aABC|bB|a B->b C->c

34 예제 7.6 S->aA A->aABC|bB|a B->b C->c 문법이 이미 Greibach 정규형
전이규칙 시작 : (q0,,z)={(q1,Sz)} 종료 : (q1,,z)={(qf,z)} 나머지 (q1,a,S)={(q1,A)} (q1,a,A)={(q1,ABC),(q1,)} (q1,b,A)={(q1,B)} (q1,b,B)={(q1,)} (q1,c,C)={(q1,)}

35 예제 7.6 aaabc를 위한 이동 (q0,aaabc,z) (q1,aaabc,Sz) (q1,aabc,Az)
시작 : (q0,,z)={(q1,Sz)} 종료 : (q1,,z)={(qf,z)} 나머지 (q1,a,S)={(q1,A)} (q1,a,A)={(q1,ABC),(q1,)} (q1,b,A)={(q1,B)} (q1,b,B)={(q1,)} (q1,c,C)={(q1,)} 예제 7.6 aaabc를 위한 이동 (q0,aaabc,z) (q1,aaabc,Sz) (q1,aabc,Az) (q1,abc,ABCz) (q1,bc,BCz) (q1,c,Cz) (q1,,z) (qf,,z)

36 PDA에 대한 문맥-자유 문법 정리 7.1의 과정을 거꾸로 적용 스택의 내용은 문장 형태의 변수 부분을 반영
이미 처리된 입력은 문장 형태의 단말인 접두부 논의를 단순하게 하기 위한 조건 조건1) npda는 단 하나의 종료 상태를 갖고 스택이 비어야만 종료 상태로 이동 가능 조건2) 모든 전이는 (qi,a,A)={c1,c2,…,cn)} 의 형태를 가짐 ci = (qj, ), 스택의 내용을 한 심볼씩 감소 ci = (qj, BC), 스택의 내용을 한 심볼씩 증가

37 PDA에 대한 문맥-자유 문법 Variable의 형식 => (qiAqj)
Npda가 v를 읽고 상태를 qi에서 qj로 바꾸는 동안 A를 스택에서 제거 (qiAqj) => v 인식 (q0zqf) => w * *

38 PDA에 대한 문맥-자유 문법 (qi,a,A)={c1,c2,…,cn)} 의 형태를 가짐
ci = (qj, ) => (qiAqj) -> a ci = (qj, BC) => (qiAqj) -> a(qiBqk)(qkCqj)

39 예제 7.7 다음 전이를 가진 npda를 고려 (q0,a,z)={(q0,Az)} (q0,a,A)={(q0,A)}
(q0,b,A)={(q1,)} (q1,,z)={(q2,)}

40 예제 7.7 (q0,a,z)={(q0,Az)} (q0,a,A)={(q0,A)} (q0,b,A)={(q1,)}
PDA -> CFG 조건1, 2 적용 => 조건1 만족, 조건 2 적용 (q0,a,z)={(q0,Az)} (q0,a,A)={(q0,A)} (q0,b,A)={(q1,)} (q1,,z)={(q2,)} (q0,a,z)={(q0,Az)} (q3,,z)={(q0,Az)} (q0,a,A)={(q3,)} (q0,b,A)={(q1,)} (q1,,z)={(q2,)}

41 예제 7.7 (q0,a,z)={(q0,Az)} (q3,,z)={(q0,Az)} (q0,a,A)={(q3,)}
(q0,b,A)={(q1,)} (q1,,z)={(q2,)} (q0Aq3)->a (q0Aq1)->b (q1zq2)-> 

42 예제 7.7 (q0,a,z)={(q0,Az)} (q3,,z)={(q0,Az)} (q0,a,A)={(q3,)}
(q0,b,A)={(q1,)} (q1,,z)={(q2,)} (q0zq0)->a(q0Aq0)(q0zq0)|a(q0Aq1)(q1zq0)| a(q0Aq2)(q2zq0)|a(q0Aq3)(q3zq0) (q0zq1)->a(q0Aq0)(q0zq1)|a(q0Aq1)(q1zq1)| a(q0Aq2)(q2zq1)|a(q0Aq3)(q3zq1) (q0zq2)->a(q0Aq0)(q0zq2)|a(q0Aq1)(q1zq2)| a(q0Aq2)(q2zq2)|a(q0Aq3)(q3zq2) (q0zq3)->a(q0Aq0)(q0zq3)|a(q0Aq1)(q1zq3)| a(q0Aq2)(q2zq3)|a(q0Aq3)(q3zq3)

43 예제 7.7 (q0,a,z)={(q0,Az)} (q3,,z)={(q0,Az)} (q0,a,A)={(q3,)}
(q0,b,A)={(q1,)} (q1,,z)={(q2,)} (q3zq0)->(q0Aq0)(q0zq0)|(q0Aq1)(q1zq0)| (q0Aq2)(q2zq0)|(q0Aq3)(q3zq0) (q3zq1)->(q0Aq0)(q0zq1)|(q0Aq1)(q1zq1)| (q0Aq2)(q2zq1)|(q0Aq3)(q3zq1) (q3zq2)->(q0Aq0)(q0zq2)|(q0Aq1)(q1zq2)| (q0Aq2)(q2zq2)|(q0Aq3)(q3zq2) (q3zq3)->(q0Aq0)(q0zq3)|(q0Aq1)(q1zq3)| (q0Aq2)(q2zq3)|(q0Aq3)(q3zq3)

44 예제 7.7 문자열 aab의 인식(pda) (q0,aab,z) (q0,ab,Az) (q3,b,z) (q0,b,Az)
(q0,a,z)={(q0,Az)} (q0,a,A)={(q0,)} (q0,b,A)={(q1,)} (q1,,z)={(q2,)} 예제 7.7 문자열 aab의 인식(pda) (q0,aab,z) (q0,ab,Az) (q3,b,z) (q0,b,Az) (q1,,z) (q2,,)

45 예제 7.7 문자열 aab의 인식(CFG) (q0zq2) => a(q0Aq3)(q3zq2) => aa(q3zq2)
(q0zq2)->a(q0Aq0)(q0zq2)|a(q0Aq1)(q1zq2)| a(q0Aq2)(q2zq2)|a(q0Aq3)(q3zq2) (q3zq2)->(q0Aq0)(q0zq2)|(q0Aq1)(q1zq2)| (q0Aq2)(q2zq2)|(q0Aq3)(q3zq2) (q0Aq3)->a (q0Aq1)->b (q1zq2)->  예제 7.7 문자열 aab의 인식(CFG) (q0zq2) => a(q0Aq3)(q3zq2) => aa(q3zq2) => aa(q0Aq1)(q1zq2) => aab(q1zq2) => aab

46 정리 7.2 만약 어떤 npda M에 대하여 L = L(M) 이면, L은 문맥-자유 언어이다 증명은 교재참조

47 결정적 PDA와 결정적 CFG

48 결정적 PDA 이동에 있어서 선택의 여지가 없는 PDA

49 정의 7.3 PDA M = ( Q, , , , q0, z, F)이 다음의 제약 조건을 만족하면 결정적 PDA
(q,a,b)는 많아야 한 개의 원소를 포함 주어진 입력 심볼과 스택 톱 심볼에 대하여 많아야 하나의 이동만이 존재 만약 (q,,b)가 공집합이 아니면, 모든 c   에 대하여 (q,c,b)는 공집합이어야 함 어떤 형상에서  전이가 가능할 경우, 어떤 입력을 사용하는 이동도 주어지지 않아야 함

50 FA와 PDA의 차이점 전이를 유지 전이가 공집합 일수도 있음 결정성 => 언제든지 많아야 하나의 가능한 이동이 존재
스택의 탑 심볼이 다음 이동을 결정하는 데 영향을 줌 => 전이 가능 전이가 공집합 일수도 있음 종말형상이 있을 수도 있음 결정성 => 언제든지 많아야 하나의 가능한 이동이 존재

51 정의 7.4 L=L(M)인 dpda M이 존재하고 오직 그럴 때에만 언어 L을 결정적 문맥-자유 언어라 한다.

52 예제 7.8 다음 언어는 결정적 문맥-자유 언어이다. L={anbn : n>= 0} => PDA가 존재함을 보임

53 예제 7.8 아래와 같은 전이를 갖는 pda M=({q0,q1,q2}, {a,b},{0,1},,q0,0,{qf})는 주어진 언어를 인식한다. (q0,a,0)={(q1,10)} (q1,a,1)={(q1,11)} (q1,b,1)={(q2,)} (q2,b,1)={(q2, )} (q2,,0)={(q0,)} M은 정의 7.4의 조건을 만족하고 따라서 결정적이다.

54 예제 7.4 비결정적 L={wwR:w {a,b)+}
npda M=({q0,q1,q2},{a,b},{a,b,z},,q0,z,{q2}) (q0,a,z)={(q0,az)} (q0,b,z)={(q0,bz)} (q0,a,a)={(q0,aa)} (q0,b,a)={(q0,ba)} (q0,a,b)={(q0,ab)} (q0,b,b)={(q0,bb)} 문자열의 중간을 추측하는 전이는 상태를 q0에서 q1 (q0,,a)={(q1,a)} (q0,,b)={(q1,b)} wR과 스택의 내용이 일치하는지를 확인하는 전이들 (q1,a,a)={(q1, )} (q1,b,b)={(q1,)} 마지막으로 성공적인 일치를 인식하는 전이 (q1,,z)={(q2,z)} 비결정적

55 오토마타의 동치 DFA  NFA PDA  NPDA

56 예제 7.9 결정적 문맥-자유 언어 L1과 L2에 대해서 L = L1 U L2 언어 L이 결정적 문맥-자유 언어 인가?
아니다. 두 언어를 인식하는 PDA에서 한 입력 심볼과 스택 심볼에 대해서 하나 이상의 전이가 존재할 수 있다.(두개의 PDA 전이 함수를 합침으로 해서 결정적 문맥-자유 언어의 합집합은 비 결정적 문맥-자유 언어가 될 수 있다)

57 결정적 문맥-자유 문법 결정적 문맥-자유 언어 DCFG의 효율적인 파싱이 가능
퇴각 검색(backtracking)이 발생하지 않으므로 파싱에 대한 컴퓨터 프로그램을 쉽게 할 수 있음 S문법의 확장인 LL문법을 이용하여 컴파일러 구현 입력을 왼쪽에서 오른쪽으로 스캔하여 좌측우선 유도를 구성하면서 파싱