이번 글에서는 지금까지 배운 내용을 토대로 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는 유한 상태 기계로, 카운팅할 수 있는 제한이 존재했다.) ..
dimer (길이가 2인 k-mer) 조합은 AA 부터 CC 까지 16가지가 존재한다.그러면 확률적으로 각각의 dimer 가 등장할 확률은 1/16으로 동일하므로, 실제 서열에서도 이와 비슷한 분포를 갖고 있어야 할 것 같다.그런데 사람 게놈을 살펴봤더니 그렇지 않았다.특히 CG 패턴은 매우 적었다.이런 현상을 가리켜 CG-Island 라고 부른다. 이 문제는 The Fair Bet Casino 문제로 비유할 수 있다.어떤 카지노 게임이 동전 던지기의 결과인 H/T 로 결과가 정해진다고 해보자. 그런데 이때 동전은 '공정한 동전 = 모두 1/2 확률' 과 '편향된 동전 = 앞면이 3/4' 이 있다. 따라서 이렇게 조건부 확률로 표현할 수 있다. 그리고 공정한 동전과 편향된 동전의 교체가 적발되면 좋지 않..
팬케이크 뒤집기 문제어떤 무작위 수열이 존재한다.내가 할 수 있는 연산은 수열의 prefix를 뒤집는 연산만 가능할 때,주어진 수열을 정렬하는데 필요한 최소한의 뒤집기 연산 횟수를 구하는 문제 그리디 접근법으로 떠올릴 수 있는 제일 간단한 해결 방법 :현재 남아있는 제일 큰 수를 맨 위로 오도록 뒤집는다 → 전체를 뒤집는다 → 제일 큰 수가 맨 밑으로 간다. 이를 반복하면 된다. 이 알고리즘은 분명 잘 작동한다.하지만 더 적은 횟수로 문제를 풀 수는 없을까? 4번에 정렬할 수 있다! 사람과 쥐의 게놈은 비슷함 (여러 번의 재배치가 존재하는 차이점이 있다.)이때 발생 가능한 재배치의 종류는 크게 4가지 1. Reversal (이번 글에서 주로 정리할 내용)2. Fusion : 2개의 contig 가..
DNA로 돌아와서, 자주 반복되는 DNA motif 를 찾거나, 가장 자주 등장하는 k-mer를 찾거나, 특정한 k-mer가 얼마나 자주 등장하는지 알고 싶을 때 문자열 패턴 매칭 알고리즘을 사용할 수 있다. 제일 근본적인 패턴 매칭 문제는 문자열에 특정 패턴이 존재하는지 확인하고, 존재한다면 그 위치는 어디인지 찾는 것 제일 나이브한 방법은 문자열을 직접 순회하면서 찾는 것이다.이때는 패턴의 길이가 n이고, 문자열의 길이가 m일 때, O(mn) 의 시간이 걸린다. 근데 이걸 조금 더 최적화 해보면,위와 같은 문자열에서 ssi 를 찾는다고 할 때, SS까지 일치했는데, i가 m이랑 불일치해서 실패한 경우,우리는 그 다음에 시도할 위치를 한번 건너뛸 수 있다.우리가 찾는 패턴의 prefix ss가 지금 ..
