🖥 Computer Science/계산이론

서론 앞서 배운 유한 오토마타와 푸시다운 오토마타를 비교해보면, 임시 저장장소의 특성이 둘 사이의 차이를 만들어냄을 알 수 있습니다. 만약 저장장소가 없다면 유한 오토마타이며, 저장장소가 스택이라면 유한 오토마타보다 더 강력한 푸시다운 오토마타를 갖게 됩니다. 만약 오토마타에 좀 더 유연한 저장장소를 더해준다면, 더욱 강력한 언어군을 발견할 수 있을 것입니다. 예를 들어 두 개, 세 개의 스택, 큐, 또는 다른 저장 장치를 사용한다면 어떤 결과가 나올까요? 각각의 저장장소는 새로운 종류의 오토마타를 정의하고, 그것을 통하여 새로운 언어군을 정의할 수 있을까요? 이러한 접근은 대부분의 경우 흥미로운 결과를 이끌어내지는 못했습니다. 가장 강력한 오토마타와 계산의 한계에 대하여 무엇을 이야기할 수 있을까요?..

문맥-자유 문법은 유한 오토마타로는 인식될 수 없으며, 푸시다운 오토마타에 의해서 인식될 수 있습니다. 푸시다운 오토마타는 오토마타와 비슷한 생김새를 지녔으나, 스택(Stack)을 추가로 사용합니다. 비결정적 푸시다운 오토마타 (NFDA) 푸시다운 오토마타는 다음과 같이 표현됩니다. 제어 유닛의 각 움직임은 입력 파일로부터 하나의 심벌을 읽고, 동시에 스택 연산을 통하여 스택의 내용을 바꿉니다. 제어 유닛의 각 움직임은 현재의 입력뿐 아니라, 현재 스택의 Top에 있는 심벌에 의하여 결정됩니다. 움직임의 결과는 제어 유닛의 새로운 상태와 스택의 톱에서의 변화입니다. 비결정적 푸시다운 인식기 (nondeterminisitc pushdown acceptor, npda)는 다음과 같이 정의됩니다. $$M = ..

CYK 알고리즘 문법이 Chomsky 정규형인 경우에만 제대로 작동하며, 다음과 같이 문제를 작은 문제로 나누어 해결하는 알고리즘입니다. Chomsky 정규형민 문법 G = (V, T, S, P)에 대하여, 문자열 w = $a_1...a_n$이 주어졌다고 하겠습니다. 문자열 w의 i번째 심벌부터 j번째 심벌까지의 부문자열을 $w_{ij}$라 하겠습니다. 즉 아래와 같습니다. $$w_{ij} = a_i...a_j$$ 또한 V의 부분집합 $V_{ij}$를 다음과 같이 정의합니다. $$V_{ij} = \left\{ A \in V \;: \; A \; \overset{*}{\Rightarrow}\; w_{ij} \right\}$$ 이때, 문자열 w는 L(G)에 속하므로, $$S \in V_{1n}$$ $V_{i..

Chomsky 정규형 Chomsky 정규형은 생성규칙의 우변에 있는 심벌들의 수를 2개 이하로 엄격하게 제한한 형태입니다. 문맥 자유 문법 G에서 모든 생성규칙이 다음의 형태를 만족하면 G를 Chomsky 정규형이라 합니다. $$A \to BC$$ 혹은 $$A \to a$$ 단 여기서 A, B, C ∈ V 이고 a ∈ T 입니다. 아래는 Chomsky 정규형의 예시입니다. $$S \to AS \;|\;a$$ $$A \to SA \;|\;b$$ 아래는 Chomsky 정규형이 아닙니다. $$S \to AS \;|\;AAS$$ $$A \to SA \;|\;bb$$ Chomsky 정규형으로 변환하기 주어진 문법 G는 람다 생성규칙과, 단위 생성규칙을 가지고 있지 않아야합니다. (가지고 있는 경우 이를 제거한 뒤..

문맥 자유 문법의 생성규칙의 우측에 나오는 문자열의 형태에는 어떠한 제약도 없습니다. 그러나 오히려 이런 제한으로 인해 복잡성이 증가하는 단점을 가집니다. 이제부터 저희는 이러한 제약 없는 문법 대신, 제한된 형태를 만족하는 동치인 문법으로 변형하는 방법을 살펴볼 것입니다. 문법의 변형 방법 빈 문자열(λ)이 나타나는 문법이나 언어는 다소 바람직하지 못합니다. 이는 많은 정리와 증명에서 별개의 역할을 하며, 특별히 주의하여야 합니다. 저희는 이러한 빈 문자열을 고려대상에서 제거하여 오직 λ를 포함하지 않는 언어만을 살펴보려 합니다. L을 문맥 자유 언어라 하고, G를 L-{λ}(L 에서 빈 문자열 제거)을 생성하는 문맥 자유 문법이라 하겠습니다. 여기서 V에 새로운 시작 심벌을 추가하고 다음의 새로운 생..

파싱(Parsing) 주어진 문자열 w가 어떠한 문법 G로부터 생성되는 언어 L(G)에 속하는지의 여부를 알아야 하는 경우가 있습니다. 이를 판별하기 위한 알고리즘을 소속성(membership) 알고리즘이라 합니다. 파싱의 의미는 L(G)에 속하는 w가 유도되는데 사용된 일련의 생성규칙을 찾는 것 입니다. 단순한 파싱 방법으로는 체계적(systematically)으로 가능한 모든 유도들을 구성해 가면서, 그 중에 w와 일치하는 것이 있는지를 알아보는 것입니다. 구체적으로, 처음으로는 다음과 같은 형태의 시작 심벌을 좌변으로 갖는 모든 생성규칙들을 살펴봅니다. $$S \to x$$ 시작 심벌 S로부터 한 단계에 유도될 수 있는 모든 문장형태 w를 찾습니다. 만약 어느 x도 일치하지 않는다면, 이후 각x의 ..

문맥 자유 언어 문법 G = (V, T, S, P)에서 모든 생성규칙이 $$A \to x$$ 의 형태를 가지면 G를 문맥-자유 문법(Context-free Grammer, CFG)이라 합니다. 이때 A와 x는 다음과 같습니다. $$A \in V, \;\;\;\; x \in (V \cup T)^{*}$$ 또한 언어 L에 대해서 L = L(G)를 만족하는 문맥-자유 문법 G가 존재하고, 오직 그럴 때에만 L을 문맥-자유 언어(Context-free Lanuage, CFL)라고 합니다. 위의 정의에 의하여 모든 정규 문법은 문맥 자유 문법이 되며 따라서 정규 언어는 문백 자유 언어임을 알 수 있습니다. 즉 정규 언어군은 문맥 자유 언어군의 진부분 집합입니다. 문맥 자유라는 이름은 문장 형태(sentencial..

지난번 글에 이어서 정규 언어에 대한 판별에 사용될 수 있는 펌핑 보조정리에 대해 알아보도록 하겠습니다. 펌핑 보조정리 (Pumping lemma) 펌핑 보조정리는 비둘기집 원리를 다른 형태로 이용한 것입니다. 이에 대한 증명은 다음 관찰에 기반을 두고 있습니다. n개의 정점을 갖는 전이 그래프에서, 길이가 n 이상인 모든 보행은 어떤 정점이 반복, 즉 사이클을 가져야 한다 펌핑 보조정리는 다음과 같습니다. L을 무한 정규 언어(infinite regular lanuage)라 하면, 다음 성질을 만족하는 양의 정수 m이 존재합니다. 다음을 만족하는 모든 문자열 w에 대하여 $$|w| \geq m, \;\;\;\;\;\; w \in L$$ 문자열 w는 아래의 조건을 만족하도록 분할될 수 있습니다. $$w ..