|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/12/09 23:49
펌핑렘마는 해당 language가 CFL에 속하지 않음을 증명하기 위해 사용됩니다.
렘마의 조건에 맞춰서 문제의 언어를 표현할 수 있는 FA(정확히는 push-down automata)가 존재할 수 없음을 모순을 통해 보여주면 됩니다. 기본적으로는 비둘기집의 원리를 이용하구요.
08/12/10 08:41
펌핑렘마 간단한 증명입니다. (그림없이 되려나 모르겠네요)
infinite regular language L을 가정하면, L을 accept하는 m개의 state를 가지는 DFA가 존재한다. w∈L인 string w를 가정하면, walk w가 존재한다. 만약 |w| ≥ m 이라고 한다면, 비둘기집 원리에 따라 walk w내의 한 state가 repeat된다. 이제 q가 repeat되는 첫번째 state라고 하자. q전까지를 x, q를 시작으로 하는 사이클을 y, q이후를 z라고 한다면, w=xyz로 쓸수 있다. w를 살펴보면, |xy| ≤ m, |y| ≥ 1, xy가 accept되고, xyz가 accept되고, xyyz가 accetp되고, 차례로 xy^iz (i = 0,1,2..)가 accept됨을 볼 수 있다. 따라서 xy^iz (i = 0,1,2..) ∈L 이다. 펌핑렘마의 적용은.. 어떤 language가 주어지면, 이 language가 regular language라고 가정합니다. 그런 후 임의의 m을 잡고, |w| ≥ m 이 되게 w를 고릅니다. 그리고 이 w를 xyz로 쓰면(임의로 xyz를 잡아줍니다), y가 반복되어도 이는 여전히 w∈L인데 (펌핑렘마에 따라) 이 결과는 기존의 L과 달라지게 됩니다. 위의 과정을 통해서 L이 regular language가 아님을 증명하면 됩니다.(Contradiction에 의해)
|
||||||||||