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

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

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

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 유한개의 심볼로 무한한 스트링을 표현하자니 트리중에 반복되는 부분이 있을 수밖에…

Pumping Lemma : 예1 ex 1)

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

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

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

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

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

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

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

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의 길이가 한정되어 있지 않기 때문이다.

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

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

Closure Properties of CFL (2)

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

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

Closure Properties of CFL (5)

Closure Properties of CFL : 예

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이 없다는 것의 의미?  나중에 철저하게 검토해 봅시다

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