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가 지금 ..

(문해기는 시간이 없어서 간결하게 정리할 예정..) 지금까지는 DNA에 대한 이야기였다면 이번에는 단백질에 대한 이야기를 해보자.단백질은 아미노산들의 조합으로 구성된다.각각의 아미노산은 탈수결합을 통해 합쳐지며, 그 결과물을 residue 라고 부른다.이때 20가지 아미노산 residue 의 분자량은 이미 정확하게 잘 알려져 있다. PIT 라는 고분자에 대해, PIT, PTI, ITP 등 순서는 분자량에 영향을 주지 않는다.따라서 이들 각각을 2개로 쪼갰을 때, (PI, IT) 와 (PT, TI) 의 분자량 합은 같다 (?) 20가지 아미노산에 대해 결합에 참여했을 때 물이 빠진 상태의 분자량을 하나의 테이블에 저장할 수 있고,이를 Daltons 이라고 부른다.  더보기 AminoAcid = { '..

흐름을 다시 정리해보면 어떤 문장이 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 ..

운영체제에서도 정리했지만, 조금씩 설명이 다른 부분이 있어서 DB에서도 추가로 정리한다. RAID여러 개의 디스크를 사용하여 장애에 대비하는 기법Redundant Array of Independent Disks 의 약자로, 여러 디스크의 배열을 두고, 데이터를 저장하는 방법이다.RAID는 논리적으로는 1개의 디스크로 보이지만, 실제 내부적으로는 여러 개의 디스크를 구성하는 것이다. RAID는 크게 2가지 개념이 있다. 1. 데이터 스트라이핑2. 중복 (redundant) 1번은 데이터를 여러 곳에 나누어 저장한다는 의미로 성능 향상에 효과적이다.2번은 데이터를 중복해서 저장한다는 의미로 장애에 강해져서 신뢰성 향상에 효과적이다.RAID는 데이터 스트라이핑과 중복을 구현한 디스크 배열이다.  사용자가 디스..