먼저 결론부터 말하자면,모든 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는 데이터 스트라이핑과 중복을 구현한 디스크 배열이다. 사용자가 디스..
Sector 구조 하드디스크의 하나의 섹터는 위와 같은 포맷으로 되어있다.우선 실제 데이터가 들어가는 부분이 제일 중요할 것이고 그 앞 뒤로는 부가 정보를 저장한다.데이터는 보통 512byte 크기가 저장된다. Preamble : bit pattern 으로 시작하며, 이 부분이 섹터의 시작임을 나타낸다.또한 실런더 넘버와 섹터 넘버와 같은 정보가 들어있다. ECC : Error-Correcting Code, read error 가 발생했을 때 복구할 수 있도록, 여분 정보가 저장되어 있다. 디스크에는 일부 섹터가 망가지는 것을 대비해서 여분의 spare sector를 남겨둔다.그리고 이와 같이 초기 세팅을 하는 것을 low-level formatting 이라고 한다. Cylinder Skew (★) ..
Hard Disk 하드디스크는 위 그림과 같이 여러 원판(플래터)이 겹겹이 쌓여있는 구조로 되어있다.그리고 원판의 앞/뒷 면에 데이터를 저장할 수 있다.이 원판이 쌓여있는 원통형 구조를 실린더라고 부른다. 플래터에서 데이터를 읽는 것은 헤드가 담당하며, 헤드는 디스크 arm 에 붙어있다.디스크 암은 좌우로 움직이면서 트랙을 이동할 수 있다. 플래터 하나는 여러개의 동심원으로 구성되어 있으며, 각각의 동심원으로 이루어진 영역을 트랙이라고 부른다.그리고 트랙은 중앙을 향하는 세로선에 의해 분할된 '섹터' 로 구성된다.왼쪽 그림을 보면 하드디스크 안쪽은 트랙당 섹터가 16개 이고, 바깥쪽은 트랙당 섹터가 32개로 되어있다.반지름의 길이가 달라지기 때문에 2가지 종류의 트랙으로 구성한 것이다. 오른쪽 그림은..
