regular language는 수학적으로 문장의 집합이다.regular language는 DFA, NFA로 나타낼 수도, Regular expression 으로 나타낼 수도, Regular Grammar로도 나타낼 수 있다. 그렇다면 우리가 수학적으로 다룰 수 있는 언어는 레귤러 랭귀지가 전부일까?또한 레귤러 랭귀지에 대한 특정 연산에 대해서 닫힌 (closure) 연산 이 존재할까? 어떤 연산이 닫혀있다는 것은 피연산자와 연산 후 결과의 집합이 같은 것을 말한다.예를 들어 두 정수를 더하면 그 결과 역시 정수이므로 정수는 덧셈에 대해 닫혀있다고 할 수 있다. 이번 글에서는 Regular Language 에 대해 Closure Properties 에 집중해서 정리해본다. 기본 연산에 대해 위 정리는 ..
Grammar 에 대해서 어떤 문법의 모든 production 이 A → xB 또는 A → x 형태로 작성된다면,이 grammar에 대해 right-linear 하다고 말한다. (A, B는 변수이고 x는 터미널이다.) 반대로 모든 production 이 A → Bx 또는 A → x 로 형태로 작성되면,이 grammar에 대해 left-linear 하다고 말한다. 이때 left-linear 또는 right-linear 한 grammar를 가리켜, Regular Grammar 라고 말한다.regular grammar는 프로덕션이 만드는 sentential form의 변수 개수가 1개 또는 0개라는 특징이 있다. 위 그림과 같은 2개의 문법을 보자.production 에 집중해서 보면,첫 번째 문법은 rig..
지난 글에서 DFA로 나타내는 언어는 regular language 이며, regular language 는 DFA로 나타낼 수 있다고 하였다.그런데 이 regular language 를 나타내는 방법 중 하나가 바로 regular expression 이었다. 따라서 위 그림과 같이, regular expression 은 DFA / NFA 로 나타낼 수 있고,반대로 DFA / NFA 가 나타내는 언어도 regular expression 을 통해 나타낼 수 있다. 이를 증명하려면, regular expression 이 나타내는 언어가 DFA가 만드는 언어의 superset 이고,반대로 DFA 가 만드는 언어가 regular expression 이 나타내는 언어의 superset 임을 보이면 된다.그러면 r..
지금까지 DFA에 대해서 정리하면서, DFA로 표현할 수 있는 언어를 regular language 라고 했었다.이때, 모든 NFA는 DFA로 변환이 가능하기 때문에 NFA로 표현할 수 있는 언어 역시 regluar language 였다.DFA로 표현가능한 언어가 regular language 라면, 거꾸로 regular language 는 DFA로 표현이 가능하다. 따라서 위 그림과 같은 관계가 성립한다.이번 글에서는 regular language를 나타내는 또 다른 방법인 regular expression 에 대해 정리해본다. regular expression 은 다음 3가지 내용으로 정의된다. 1. φ, λ, a ∈ Σ (알파벳에 포함되는 하나의 심볼) 3가지는 모두 regluar expressi..
다음 2개의 명제가 참인지 거짓인지 생각해보자. 1. DFA가 받아들이는 언어는 유일하다. (O)DFA가 받아들이는 (생성하는) 언어는 유일하다.(그리고 그 언어는 regluar 하므로, regular language 라고 할 수 있다.) 2. Regular Language 가 주어질 때, 이 언어를 만드는 DFA는 유일하다. (X)이 명제는 위 명제의 역인데, 이 명제는 틀렸다.하나의 언어를 받아들이는 (만드는) DFA는 여러개가 존재할 수 있다.같은 언어를 만들어내는데, 10개 state로 구성된 DFA를 만들 수도 있고, 20 state 로 구성된 DFA를 만들 수도 있다.따라서 이로부터 어떻게 하면 같은 언어를 만들더라도 최소한의 상태를 사용해서 만들 수 있을지 고민할 수 있다. 왼쪽의 DFA..
인덱스는 결국 레코드를 빠르게 식별하기 위해 레코드 정보인 rid 를 갖고 있는 추가적인 데이터이다.이 데이터 하나하나를 가리켜 '데이터 엔트리' 라고 부르며 이 정보드는 인덱스 파일에 저장되어 있다.인덱스 파일도 레코드를 저장하는 파일처럼 여러 인덱스 엔트리의 집합으로 구성되어 있고, '페이지' 로 구분된다. 이번에는 정렬되어 있는 데이터 엔트리 중에서 내가 찾으려는 데이터 엔트리를 빠르게 찾기 위한 방법을 정리해본다.데이터 엔트리를 빠르게 찾기 위해 데이터 엔트리를 특별한 방법으로 젖아할 수 있는데, 크게 트리 기반 인덱스와 해시 기반 인덱스로 나뉜다.이번 글에서는 먼저 트리 기반 인덱스에 대해 정리해본다. 트리 기반 인덱스트리 기반 인덱스는 특정 탐색 키 값을 트리의 노드로 갖고 있다. (이를 가리..
파일DBMS가 데이터를 다룰 때는 '파일(file)' 로 추상화하여 다룬다.파일은 레코드들의 집합이며, 하나 이상의 페이지로 구성되어 있다.그림으로 보면 이해가 쉽다. DBMS가 다루는 파일은 여러 개의 레코드로 이루어져있다.(이 레코드는 테이블에 저장되는 하나의 데이터 레코드와 비슷한 의미로 이해했다.) 이때 파일은 여러 레코드를 가지는 페이지로 나누어진다.메모리에 적재되어 실행중인 DBMS 프로그램이, 디스크에 저장된 레코드를 메모리로 읽어오거나, 처리한 레코드를 디스크에 쓸 때는 항상 페이지 단위로 주고 받는다.데이터베이스에서 읽어오는 페이지는 1KB ~ 8KB 까지 다양한 크기가 존재할 수 있는데, 페이지의 크기는 보통 4KB 또는 8KB 이다. 레코드에는 그 레코드를 식별할 수 있는 레코드 I..
하드 디스크의 구조 하드 디스크는 여러개의 원판이 겹겹이 쌓인 구조를 하고 있다.각 원판 중앙에는 spindle rod 라는 중심축이 있고, 각 원반은 중심축을 기준으로 회전한다.이 원반을 platter 라고 부르고, 플래터에 들어있는 0과 1로 이루어진 데이터를 r/w arm 이 읽어들인다.이때 데이터를 읽기 위해서는 각 arm이 물리적으로 이동을 해야 하는데, 디스크 플레이트는 여러개의 트랙으로 구분되고, 그림에서 보는 것처럼 원반을 부채꼴 모양으로 자른 섹터로 나눌 수도 있다. 데이터를 읽고 쓸 때는 하나의 플레이트에서 색터와 트랙이 만드는 영역에 저장되는 '블록' 단위로 데이터를 읽고 쓴다.따라서 데이터를 찾는 데 걸리는 시간은 트랙을 이동하는 시간과 회전하여 섹터를 찾는 시간의 합으로 나타낼 수..
그림과 같이 스레드가 구현되어 있다고 해보자.(이 구현은 user level 스레드를 보여주고 있다. 런타임 시스템과 그 내부에 스레드 테이블이 있기 때문이다.) 이때 각각의 프로세스에게는 50ms 의 퀀텀이 주어졌고, 각 스레드는 CPU burst 마다 5ms의 시간이 소모된다고 해보자. 그러면 커널이 먼저 실행할 프로세스를 고르고, 그 다음에 런타임 시스템이 실행할 스레드를 골라서 굴리므로 프로세스 A의 스레드들이 A1 A2 A3 A1 A2 A3 이런식으로 돌아간다.유저 레벨 스레드는 스레드 스위칭이 빠르므로, thread_yield 와 같은 프로시저를 사용하여 빠르게 스레드를 교체하며 돌리는 것이 가능하고, 성능도 좋다. (다만 라운드 로빈과 같이 정해진 퀀텀을 정해두고 돌리는 것은 힘들다.) 이때..
스레드를 구현하는 방법은 User space 에서 구현하거나, Kernel space 에서 구현하거나, 두 방법을 섞는 하이브리드 방법 크게 3가지가 있다. 각각의 구현 방법에 대해서 정리해본다. User Space 메모리 공간은 크게 User space 와 Kernel space 로 나뉜다.유저 스페이스는 일반적인 유저 프로세스가 실행되는 공간이고, kernel spaces는 운영체제의 핵심 요소인 커널이 존재하며 실행되는 공간이다. User space 에서 스레드를 구현하는 경우 위 그림과 같이 구현할 수 있다.이때 운영체제는 실제로 멀티스레드가 가능한 환경으로 동작하지만, 커널은 스레드의 존재를 모르고, 기존의 프로세스 모델에서 프로세스를 다루는 것과 비슷하게 돌아간다. 따라서 커널에는 proce..
