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

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

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

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?

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

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

CFL  npda : 예1

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

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

CFL  npda : 예2

CFL  npda : 일반적인 경우

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

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

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

CFG  npda : 정리 pf) Show by induction

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

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

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

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

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

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

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

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