학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습

Presentation on theme: "학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습"— Presentation transcript:

1 학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습
제 7장. Pushdown Automata 학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습 CFL  pda의 변환에 대한 연습 필요

2 개요 FA의 한계  극도로 제한된 메모리  unlimited counting capability
+ matching a sequence of symbols in reverse order  STACK! Nondeterministic pda CFL  npda 변환 dpda와 deterministic CFL deterministic CFL를 위한 문법과 파싱

3 Nondeterministic Pushdown Automata
FA와 비교하여 기본 정의를 숙지할 것! Nondeterministic Pushdown Automata λ -transition  L = {anbn : n>=0} + {a}

4 Language Accepted by PDA
(q, w, u) : instantaneous description of pda move (q1, aw, bx) (q2, w, yx) iff (q2, y) ∈ δ (q1, a, b) cf) Def. language accepted by M state unread input stack contents irrelevant 예1) L={w : na(w) = nb(w)} a  0 push, 1 pop b  0 pop, 1 push 예2) L={wwR} middle?

5 NPDA : Exercises 7.1 4 (a), (d), (g), (j) : CFL  npda 구하기. 좀 많은가?
14 : 모범답안을 참고하면서…

6 CFL  npda CFL npda Basic idea : npda carrying out a leftmost derivation of strings variables in right part → stack terminals in left part → input read Greibach NF i) start symbol → stack ii) ∀A → ax

7 CFL  npda : 예1

8 CFL  npda : 정리 end of derivation stack no. steps in derivation

9 CFL  npda : 증명 let stack contents = unmatched part of sentential form

10 CFL  npda : 예2

11 CFL  npda : 일반적인 경우

12 CFG  npda : 기본 아이디어 stack contents = variable part of sentential form
processed input = terminal prefix of sentential form stack contents internal state sentential form representing

13 CFG  npda : 기본 아이디어 - Example 7.7 : p. 191

14 CFL  npda : 정리 sentential form
leftmost qi : current state middle symbols : stack content

15 CFG  npda : 정리 pf) Show by induction

16 CFL  npda : Exercises 7.2 3 : CFL  npda 변환 연습
5 : Greibach NF을 일단 변환하고… 15 : npda  CFG 변환연습

17 Deterministic Pushdown Automata & DCFL
Deterministic pda의 핵심은 각 순간에 선택의 여지가 없음을 다시 한번 상기할 것.

18 dpda & DCFL 이 언어는 대표적인 CFL이지만, dpda로는 처리할 수 없음을 이해합시다.

19 dpda & DCFL 좀 헷갈리게 정리되어 있지만, 핵심은 L이 deterministic이라고 가정하면
an bn λ bn cn M 좀 헷갈리게 정리되어 있지만, 핵심은 L이 deterministic이라고 가정하면 이미 알려진 사실(anbncn이 not CFL)이 위배됨을 보인다.

20 dpda & DCFL : Exercises 7.3 1 : example 7.8의 아류문제
8 : 답은 deterministic인데…

21 Grammars for DCFL DCFL은 실제 PL에서 널리 사용하는 언어이므로 특히 효율적인 파싱이 중요함
no backtracking A → ay parsing top-down → LL grammar : input scanned left → right leftmost derivation

22 Grammars for DCFL : 예 좀더 powerful하기는 한데, 내용이 automata의 범주를 벗어나니
컴파일러에서 다룹시다

23 Grammars for DCFL : Exercise 7.4
8 : 생각만… 9 (a) : 생각만…