pumping lemma를 이용한 non-CFL 증명모순법으로 증명하자! 해당 language가 CFL이라 가정 그럼 당연히 CFG가 존재하고 pumping lemma를 만족해야 함 그러나 pumping lemma에서 모순 발생 -> CFL이 아님 증명 방법CFL이라 가정해당 CFL을 recognize하는 CFG가 존재pumping lemma를 만족함pumping length p가 존재어떤 "증명하기 좋은" s를 잡음pumping lemma 적용 후 모순예) $A = {a^n b^n c^n \ | \ n \ge 0}$이 CFL이 아님을 증명해라A를 CFL이라 가정하자.따라서 A는 pumping lemma를 만족하며, pumping length p가 존재한다.이때 s = $a^pb^p..

이전 regular language에서 pumping lemma가 존재했듯,context free language에서도 pumping lemma가 존재한다. Pumping lemma of CFLA가 CFL이라면, p라는 숫자가 존재해 (pumping length)s ∈ A이고 |s| >= p인 모든 s에 대해다음을 만족하는 s의 어떤 분할 u, v, x, y, z가 존재한다.i >= 0일때, $uv^{i}xy^{i}z \in A$|vy| > 0즉, v, y중 적어도 1개는 ε이 아님|vxy| 모든 CFL은 pumping lemma를 만족한다.-> 즉, 어떤 language가CFL이 아님을 대우로 증명할 수 있다! CFL => pumping lemma 만족 대우: pumping lemma 불만족..

CFG와 PDA는 동일한 힘을 가졌다즉, CFG가 나타내는 CFL을 PDA도 accept할 수 있고PDA가 recognize하는 language를 CFG가 만들 수 있다! CFL -> PDAA가 CFL이라 한다면 CFG가 존재한다이 CFG가 생성하는 language를 어떤 PDA가 전부 accept하면 된다. 문제점어떤 rule을 따를지 어케앎?-> nondeterminism을 이용하셈모든 rule을 따르게 분기를 만든다변수가 stack 가운데에 박히면 어떻게 접근함?-> 변수를 stack 최상위에 위치하게 하셈변수 위의 terminal들은 input과 match시켜 stack에서 뺴버리기변환 과정 총 3개의 state($q_{start}, q_{loop}, q_{accept}$)로 만든다스택에 $..

pushdown automataNFA + stack처럼 행동(만약 stack이 가물가물하면 [[5 자료구조 정리]] 참고)PushDownAutomata (PDA)NFAnondeterministic하다물론, deterministic한 DPDA가 있지만, 이건 일반적인 PDA(NPDA)보다 힘이 약하다stackstack의 크기는 무한top에서 쓰거(push)나 읽은 후 지울(pop) 수 있음-> 무한한 정보를 저장 가능 수학적 정의정의 ($Q$, $\sum$, $\Gamma$ $\delta$, $q_0$, $F$)$Q$: 상태의 유한 집합$\sum$: input alphabet의 유한 집합$\Gamma$: stack alphabet의 유한 집합$\delta$: transition function$\delta..

R.L -> CFLcontext free language가 regular language보다 더 넓은 범위라 했는데 그럼 regular language를 context free grammer로 표현할 수 있지 않을까? CFG 디자인 팁어떤 language를 CFG로 표현는 정형화된 방법은 딱히 없다...그러나 좀 더 쉽게 바꾸는 팁은 있다!1. 대부분의 CFL은 간단한 CFL의 모음이다각각의 CFG을 만들고 S1 -> ... S2 -> ... S -> S1 | S2 | ... 이렇게 합쳐버리기 예) ${0^n1^n \ | \ n \ge0} \cup {1^n0^n\ \ | \ n \ge 0}$을 CFG로 바꾸셈 일단 각각을 만들고 그 다음 합치자! - ${0^n1^n \ | \ n \..

이전에는 R.L에 대해 다뤘고, 이번에는 그보다 더 넓은 범위인 Context-Free-Language를 다루고자 한다. Context Free Grammer교체규칙의 모음 (꽤 재귀적임) 예) A -> 00B (A를 00B라는 걸로 교체하시오) 이떄, 같은 variable이라면 이렇게 연결해서 쓸 수 있다 A->B, A->C를 A->B|C 이렇게variable(A, B...): 실제 다른 것으로 교체되는 부분start variable: 시작하는 변수 (명시되있지 않으면 맨 첫줄의 왼쪽 변수)terminal($\sum$): 변수가 아닌 alphabet이떄, context free grammer로 생성될 수 있는 모든 문자열의 집합을 context free grammer라고 한다.규..

pumping lemma를 이용한 nonregular 증명모순법으로 증명하자! 해당 language가 r.l이라 가정 그럼 당연히 pumping lemma를 만족해야 함 그러나 pumping lemma에서 모순 발생 -> r.l이 아님 증명 방법regular language라 가정pumping lemma를 만족함pumping length p가 존재어떤 "증명하기 좋은" s를 잡음pumping lemma 적용 후 모순예) $B = {0^n 1^n \ | \ n \ge 0}$ 이 regular language가 아님을 증명해라B를 regular language라 가정하자.따라서 B는 pumping lemma를 만족하며, pumping length p가 존재한다.이때 s = $0^p 1^..

nonregular languagefinite automata나 regular expression으로 나타내지 못하는 language이걸 어케 증명하지? 일일히 DFA를 그리는 시도를 해볼까? -> 응안돼pumping lemmaA가 regular language라면, p라는 숫자가 존재해 (pumping length)s ∈ A이고 |s| >= p인 모든 s에 대해다음을 만족하는 s의 어떤 분할 x, y, z가 존재한다.i >= 0일때, $xy^{i}z \in A$|y| > 0|xy| 모든 regular language는 pumping lemma를 만족한다.-> 즉, nonregular를 대우로 증명할 수 있다! regular language => pumping lemma 만족 대..

GNFAregular expression을 label로 가진 NFA한번의 trans에 symbol의 집합을 읽는다특징start statestart state -> 모든 state로 연결∅ -> start state (어떤 state에서도 start로 못 돌아옴)accept state모든 state -> accept state로 연결accept state -> ∅ (accept에서 다른 state로 못 돌아옴)일반 statestart 빼고 전부 다 연결자기 자신, 다른 일반 state, accept와 연결만드는 법 (DFA -> GNFA)새로운 start, accept 잡기transition 모두 연결ε, ∅를 활용!이떄, 원래 start, accept였던 것은 각각 새로운 start, accept에 ε로..

모든 regular expression은 regular language를 recognize할 수 있는가?모든 regular language는 regular expression으로 표현될 수 있는가?-> 참 (즉, r.e와 DFA, NFA는 모두 표현력이 같다.) Regular expression -> Regular language 증명즉, regular expression이 NFA로 표현됨을 증명 기본 규칙에 대한 NFAr.e의 기본 요소들은 NFA로 충분히 나타낼 수 있다.{a}, $단, \ a \in \sum$N = (${q_1, q_2}$, $\sum$, $\delta$, $q_1$, ${q_2}$)단, δ(q1, a) = q2, (단, δ(r, b) = ∅ {r≠q1, a≠b}εN = (${q_1..

regular expressionregular operation을 이용해서 regular language를 표현할 수 있다!피연산자는 집합의 형태이다.간혹가다 그냥 알파벳에 0∪1처럼 쓸 때가 있는데이렇게도 쓴다고 한다... 실제는 {0}∪{1}이다.연산 우선순위starconcatunionconcat은 생략 가능하다AºB = AB regular expression의 정의기본 규칙{a}, $단, \ a \in \sum$ε∅귀납적 규칙$(R_1 \cup R_2), \ 단, \ R_1, \ R_2$가 regular expression$(R_1R_2), \ 단, \ R_1, \ R_2$가 regular expression$(R_1^*), \ 단, \ R_1$가 regular expression주의) ε와 ∅는 ..