pumping lemma는 langauge가 nonregular함을 보일 때 자주 이용하는 lemma이다. pumping lemma는 다음과 같다.
증명은 비둘기집 원리(pigeonhole principle)를 이용해 증명한다.
따라서 모든 regular language는 pumping lemma를 만족한다.
'공부한것들(주마다업뎃) > Computation theory' 카테고리의 다른 글
| computation theory (6) - equivalence of CFG and PDA (0) | 2018.09.01 |
|---|---|
| computation theory (5) - context-free grammar and pushdown automata (0) | 2018.08.27 |
| computation theory (3) -regular expression (0) | 2018.08.26 |
| computation theory (2) - Equivalence of NFAs and DFAs (0) | 2018.08.26 |
| computation theory (1) -DFA, NFA (0) | 2018.08.25 |