학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해

Presentation on theme: "학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해"— Presentation transcript:

1 학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해
제 8장. Context-Free 언어의 특성 학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해  Regular 언어에서의 특성과 유사점/ 상이점을 집중적으로 이해할 것

2 개요 언어계통에서 CFL의 위상을 점검해 봅시다 Regular deterministic CFL CFL
context sensitive 2 pumping lemmas Closure properties and decision algorithms for CFL

3 Two Pumping Lemmas CFL를 위한 펌핑 렘마를 다시 정의해 봅시다 Thm 8.1
 Regular 언어의 경우와 비교해 보면 뭐가 다른가요?

4 Pumping Lemma : 증명 Pf L-{λ} without unit-productions / λ-productions
|derivation| ≥ |w| / k L: infinite, G: finite → some variables repeat s A x v y u z m 유한개의 심볼로 무한한 스트링을 표현하자니 트리중에 반복되는 부분이 있을 수밖에…

5 Pumping Lemma : 예1 ex 1)

6 Pumping Lemma : 예2 ex 2) m a...ab...ba...ab...b u v x y z ex 3)
Regular 언어의 펌핑렘마와 동일하게 증명 (p. 119) RL < CFL

7 Pumping Lemma : 예3 a...a...a...ab...b...b...b ex 4) u v x y z m2 m k1

8 또 다른 Pumping Lemma : Linear CFL
Def 8.1 cf) linear grammar : at most one variable on right side of production ex)

9 또 다른 Pumping Lemma : 정리 Thm 8.2
cf) left or right ends of w to be pumped

10 또 다른 Pumping Lemma : 예 ex) linear context-free

11 2 Pumping Lemmas : Exercises 8.1
* Regular언어를 위한 pumping lemma에 비해 CFL의 pumping lemma는 상대방의 choice가 훨씬 복잡하다는 점을 제외하고는 동일하게 적용할 수 있다! - 7 (b), (d), (e) : Pumping lemma를 사용한 CFL가 아님을 보이는 좋은 예 - 11 : 복합적인 적용문제

12 CFL에 대한 Pumping Lemma 응용
CFL에 대한 pumping lemma를 응용할 때, regular language에 대한 pumping lemma와 다른 점에 유의할 필요가 있다. Regular language의 경우 pump 할 곳 (즉, w = xyz 내의 y) 은 선택한 string w 의 길이 n인 prefix 내에 한정되어 있다. 반면, CFL의 경우 pump 할 곳 (w = uvxyz 내의 v와 y)은 string u와 z의 길이에 제한이 없으므로 조건 |vxy|  m, 즉 넓이가 최대 m인 창(window) 이 있을 수 있는 위치이면 어디든지 가능하다. String vxy 는 w의 prefix가 될 수도 있고 suffix가 될 수도 있다. 따라서 CFL에 대한 pumping lemma를 이용하여 어떤 language L이 CFL가 아님을 증명하는 과정에서 조건을 만족할 수 없음을 보일 때, vxy가 있을 수 있는 w 상의 많은 경우를 모두 고려해야 한다. w vxy

13 CFL에 대한 Pumping Lemma: 증명
증명. 증명의 바탕이 되는 개념을 설명하기 위하여 간단한 예를 들기로 한다. 다음 Chomsky normal form 의 CFG를 고려하자. S  AB A  DE B  FD E  FG G  DB | g F  HG D  d H  h 이 CFG의 언어의 크기는 무한 함을 쉽게 알 수 있다. 예를 들면, rule B  FD, F  HG, G  DB 에 의하여 B가 F를 생성하고, F가 G를, 그리고 G가 다시 B를 생성하기 때문에 무한히 많은 string을 생성할 수 있다. 이 CFG 의 언어에 속한 string w = d(hd)3hg(d)3dghdghd 에 대한 parse tree를 분석하여 보자 (다음 쪽 그림 참조). Parse tree의 가장 긴 줄기에 해당하는 path label 에 반복하는 pattern F-G-B 가 있음을 알 수 있다. 이러한 반복 pattern은 grammar의 nonterminal symbol의 수가 한정되어 있는 반면, grammar가 발생하는 string의 길이가 한정되어 있지 않기 때문이다.

14 w = d ( h d )3 h g (d)3 d h g d h g d u v w x y S AB A DE E FG G
DB | g F HG D d H h B  FD

15 Closure Properties of CFL (1)
RL와는 달리 CFL의 경우 Closure 특성이 쉽게 만족되지 않는 경우가 많음 closed under union, concatenation and star-closure

16 Closure Properties of CFL (2)

17 Closure Properties of CFL (3)
not closed under intersection and complementation

18 Closure Properties of CFL (4)
closed under regular intersection

19 Closure Properties of CFL (5)

20 Closure Properties of CFL : 예

21 Some Decidable Properties of CFL
Algorithm to see if L(G) is empty - Algorithm to see if L(G) is infinite - CFL L1 = L2 ? S is useless  L(G) is empty G has repeating variables  dependency graph has cycle  L(G) is infinite No algorithm 주어진 문제를 해결할 algorithm이 없다는 것의 의미?  나중에 철저하게 검토해 봅시다

22 Closure Properties of CFL : Exercises 8.2
- 6 : Language Family간의 Closed 특성을 포괄적으로 이해합시다 - 10 : 간단하지만 한번 생각해서 풀어봅니다 - 19 : 답은 YES, 하지만 construction은 좀 지저분하지요…