이번 글에서는 지금까지 배운 내용을 토대로 RL, CFL, TM 을 비교해본다. aⁿ 은 레귤러 언어로서, DFA로 그릴 수 있었고, RE로 표현할 수도 있었고, 위와 같은 RG로 표현할 수도 있었다.(RG는 Linear Grammar 중에서 변수가 왼쪽에만 있거나, 오른쪽에만 있는 형태이면 된다.) CFL 의 경우, 대표적인 예시가 aⁿbⁿ 으로, 펌핑 렘마를 통해 RL 가 아님을 보일 수 있었고,CFG 를 통해 표현하거나, NPDA를 통해 표현할 수 있었다. 마지막으로 CFG 가 아닌 언어로 대표적인 것이 aⁿbⁿcⁿ 이었다. (이때, n ≥ 1 이어야 한다. 튜링머신은 λ를 취급하지 않기 때문)이 언어는 펌핑 렘마를 통해 CFL이 아니라는 것을 보일 수 있었고, 지난 글에서 마지막 예제 문..
지금까지 RL, CFL 을 다루었지만, 그것에도 속하지 않는 언어들이 있었다.예를 들면 aⁿbⁿcⁿ 과 같은 언어나, ww 와 같은 언어가 있었다. 그렇다면 이런 언어들은 기계로 표현할 수 없을까?저장공간이 스택이 아니라 다른 형태의 저장공간을 쓰면 이런 언어를 기계로 표현할 수 있지 않을지 생각해볼 수 있다.그래서 이런 언어를 표현하기 위한 새로운 기계로 Turing Machine 을 알아보자. Turing Machine 튜링 머신은 위와 같은 구조로 되어있다.튜링 머신에는 input file 이 별도로 없고, 컨트롤 유닛과 매우 긴 테이프가 하나 존재한다.테이프의 셀 하나에는 '테이프 심볼'이 하나 들어간다. 튜링머신은 위와 같이 정의한다.PDA에서 감마(Γ)는 스택 심볼이었다면, 튜링머신에서는 테..
CFL Clousure PropertyCFL은 다음에 연산에 대해 닫혀있다. (다음 연산의 수행 결과 역시 CFL이다.) 1. UnionCFL 2개를 합친 언어도 CFL 이다. 2. Concatenation2개 CFL 에 속하는 모든 문장을 이어붙여 만든 언어도 CFL이다. 3. Star Clousure하나의 CFL에 *를 취해도 여전히 CFL이다. 하지만 다음에 대해서는 닫혀있지 않다.1. Intersection2. Complementation 닫혀지 있지 않다는 것은 CFL일 수도 있고, 아닐 수도 있다는 뜻이다.예를 들어 CFL인 L1 과 L1을 교집합하면 여전히 CFL이다. RL와 비교해보면 위와 같다.RL에서는 교집합, 여집합에 대해서도 닫혀있었지만, CFL은 아니다. L1 과 L2는 모두..
Pumming LemmaRL와 관련된 Pummping Lemma 를 정리하면서, 펌핑 레마를 통해 이 언어가 적어도 RL는 아니다! 라는 것을 보일 수 있다고 하였다.CFL에도 펌핑 레마가 있다. 그리고 결론만 말하면 CFL에서도 펌핑레마를 통해 이 언어가 적어도 CFL은 아니다! 라는 것을 보일 수 있다. RL에서는 어떤 문장을 3조각 내서 펌핑레마를 적용했다.CFL에서는 어떤 문장을 5조각 내서 펌핑레마를 적용한다. RL에서 유한집합의 언어라면 RL인지 판별하는 것이 쉽다고 했었다. (정리글 참고)같은 이유로 CFL에서도 유한집합의 언어라면 CFL인지 판별하는 것이 쉽다. 따라서 RL에서 그러했듯, 이번에도 무한집합인 CFL에 대해서만 판별하는 방법을 생각해본다고 하자.CFL의 크기가 무한집합이라면 ..
지금까지는 CFL을 나내는 기계인 NPDA에 대해 정리했다.RL에서 DFA와 NFA가 있었던 것처럼, PDA에도 NPDA와 DPDA가 있다.이번 글에서는 deterministic PDA, DPDA와, 이 기계가 만드는 언어인 DCFL에 대해 정리해본다. DPDA 새로운 기계를 배우기에 앞서 이제부터 새롭게 배울 기계를 포함하여 지금까지 다룬 기계를 정리해보면 위와 같다.DFA는 특정 상태에 특정 input symbol 을 읽으면 어떤 상태로 넘어갈 지 반드시 결정할 수 있는, 상태의 개수가 유한한 기계였고,NFA는 특정 상태에 특정 input symbol 을 읽으면 어떤 상태로 넘어갈 지 결정할 수 없을 수도 있는, 상태의 개수가 유한한 기계였다. DFA는 트랜지션 함수를 정의할 때 모든 상태와 모든 심..
먼저 결론부터 말하자면,모든 NPDA로 만들어지는 언어는 CFL이고,모든 CFL은 그 언어를 만드는 NPDA가 존재한다.즉, nondeterministic pushdown automata 와 CFL은 equivalent 하다. 이번 글에서는 이를 한 쪽씩 증명해볼 것이다. CFL → NPDACFL의 문법을 normal form 으로 변환하는 과정에서 살펴본 폼중에 GNF가 있었다.CNF는 파싱하는데 도움을 주었고, CYK 알고리즘에 사용되었다면GNF는 CFL을 NPDA로 나타내는데 도움이 된다. 모든 λ-free CFL은 그 문법을 GNF 형태로 변환할 수 있다.GNF로 변환된 문법은 다음과 같이 NPDA로 나타낼 수 있다. GNF에서 사용되는 프로덕션 A → xB 에 대하여 다음과 같이 표현할 수 있다..
지금까지 CFG와 CFG를 통해 만드는 언어 CFL, 그리고 어떤 문장이 CFL에 속하는지 판단하는 파싱, 파싱을 편하게 하기 위한 문법 변환 방법들과 DP 알고리즘으로 파싱하는 CYK 알고리즘을 알아보았다. 이번 글에서는 마치 RL을 DFA와 NFA로 나타낼 수 있었던 것처럼, CFL을 표현하는 기계를 정리해본다.CFL은 PushDown Acceptor(PDA) 로 표현할 수 있다. 위에 적은 말을 그림으로 표현하면 위와 같다.CFL에서는 regular expression 에 해당하는 요소는 존재하지 않는다. CFL을 표현하는 NPDA는 제한없이 개수를 카운팅할 수 있거나, 시퀀스의 순서를 저장할 수 있어야 한다.(기존의 DFA, NFA는 유한 상태 기계로, 카운팅할 수 있는 제한이 존재했다.) ..
흐름을 다시 정리해보면 어떤 문장이 CFG에 포함되는지 판별하기 위해서 파싱을 활용할 수 있는데,CFG는 너무 자유도가 높아서 파싱 시간이 오래걸리고, 심지어 끝나지 않을 수도 있다. 따라서 이 문제를 해결하고자 지난 글에서는 CFG의 문법을 단순화하기 위해λ-production, unit-production, useless production 순으로 필요없는 프로덕션을 제거하였다. 이번 글에서는 CFG의 특수한 형태를 갖는 노말 폼 형태의 문법을 통해 간단하게 파싱할 수 있도록 표현하는 방법을 정리한다. Chomsky Normal Form모든 production 이 다음 형태를 가지면 참스키 노말 폼이다. 1. A → BC ( A, B, C 는 변수)2. A → a (a는 터미널) 예를 들어 6.7 ..
기존의 CFG는 화살표 왼쪽 부분만 single variable 이기만 하면 되므로 문법 표현이 자유로웠다.하지만 그런 문법으로 표현하는 언어는 너무 자유도가 높아서 파싱하는데 시간이 오래 걸리는 단점이 있었다.(지난 글에서 p^(2w+1) 으로 계산했었다.) 그래서 이번 글에서는 파싱을 좀 더 편하게 하기 위해 CFG가 표현할 수 있는 언어의 범위를 제한하지 않으면서 문법을 간단하게 바꿀 수 있는 방법들을 정리해본다. 우선 첫 번째 방법은 기존의 CFG 문법을 유지하면서 이 문법을 단순화 하는 방법을 알아본다.두 번째 방법으로는 normal form 으로 바꿔서 문법을 표현하는 방법을 알아본다. 이때 편의를 위해서 지금부터 변환하는 문법은 모두 문장으로 λ 를 갖지 않는, λ-free language ..
이번 글에서는 CFL라는 새로운 종류의 언어에 대해 어떤 문장이 이 CFL에 속하는지 판별하는 방법을 알아보자.먼저 결론을 말하면, CFL에 대해 membership을 판단할 때는 parsing을 통해 판단할 수 있다. Parsing파싱은 L(G)에 속하는 문장 w를 유도하는 production 의 나열을 찾는 것을 말한다. 위와 같은 문법이 주어졌을 때, aabb 와 abb가 이 문법으로 만들어지는 언어에 포함되는지 확인해보자. (membership problem)CFL에서 멤버쉽을 따질 때는 파싱 알고리즘으로 주어진 문장이 L에 포함되는지 확인할 수 있다.파싱을 했더니 w를 유도하는 production 시퀀스가 존재했다면 멤버인 것이고, 아니라면 멤버가 아닌 것이다. 1. aabbaabb는 다음과..
