🖥 Computer Science/계산이론

비정규 언어의 식별 정규 언어는 무한 집합일 수 있습니다. 그러나 정규 언어는 정의에 따라 유한 오토마타에 의해 인식이 되며, 이는 정규 언어의 구조에 어떠한 제약을 부여하며, 따라서 어떤 언어가 정규 언어가 되기 위해서는 이러한 제약을 따라야 합니다. 저희는 주어진 언어에 대하여 이것이 정규 언어가 아님을 증명하는 방법들을 배울 것입니다. 다음과 같은 방법이 있습니다. 비둘기집 원리 펌핑 보조정리 (pumping lemma) 비둘기집 원리 (피전홀 원리) 비둘기집의 개수를 m, 비둘기의 수를 n이라 하였을 때, m < n 인 경우 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어가 한다는 원리입니다. 비둘기집 원리를 이용하여 다음 언어가 정규 언어인지 아닌지 확인해보도록 하겠습니다. $$L = ..

서론 저희는 지금까지 정규 언어가 무엇인지에 대해서 배웠고, 정규 언어를 표현하기 위해 정규 표현, 유한 오토마타와 정규 문법을 배웠으며 이들 상호간에 변환하는 방법을 알아보았습니다. 지금부터는 모든 정규 언어들이 가지는 성질에 대해 알아보고자 합니다. 정규 언어들에 합집합, 교집합 등의 연산을 취해 생성되는 새로운 언어들은 어떤 특징들을 가지는지, 어떤 언어가 정규 언어인지 아닌지를 어떻게 보일 수 있는지에 대해 알아보겠습니다. 모든 형식 언어(formal language)는 정규 언어가 아닙니다. 이를 증명하기 위해 정규 언어의 특성을 깊이 이해하고 정규 언어를 포함하는 전체 언어들이 어떠한 성질을 가지고 있는지를 확인해야 합니다. 저희는 앞으로 다음 질문들에 대한 해답을 찾아갈 것입니다. 정규 언어..

정규 언어를 묘사하는 세 번째 방법으로 간단한 문법을 사용하는 방법이 있습니다.   우선형 문법과 좌선형 문법문법 $G = (V, T, S, P)$ 에서 모든 생성규칙들이 다음의 형태를 갖는 경우 이를 우선형(right-linear) 문법이라 합니다.$$A \to xB$$$$A \to x   \;\;\;\;\;\; A,B \in V, \;\; x \in T^{*}$$  또한 문법의 생성규칙들의 다음의 형태를 갖는 경우 이를 좌선형(left-linear) 문법이라 합니다.$$A \to Bx$$$$A \to x$$  정규 문법은 우선형 문법 혹은 좌선형 문법입니다. 정규 문법에서는 모든 생성규칙의 우변에 변수(Variable)가 최대 하나까지만 있을 수 있으며,정규 문법의 ..

서론 https://ttl-blog.tistory.com/562?category=926966 [계산이론] - 언어, 문법, 오토마타 언어 (Languages) 우리들은 이미 자연 언어(natural languages)를 사용하고 있으며, 이러한 개념과는 친숙합니다. 그러나 "언어"라는 단어에 대해서 설명을 하라고 한다면, 이는 생각보다 어려울 것입니 ttl-blog.tistory.com 해당 포스팅의 마지막에서 촘스키 계층에 대해 조금 살펴보았습니다. 촘스키 계층에는 무제한(unrestricted) 문법, 문맥연관(context-sensitive) 문법, 문맥자유(context-free) 문법, 정규(regular) 문법이 있었습니다. 이번 포스팅에서부터 저희는 정규 문법에 의해 생성되는 언어인 정규 언..

변환기(transducer) 변환기는 출력이 있는 유한 오토마타이며, 그 종류로는 밀리 기계와 무어 기계가 있습니다. Mealy 기계(Mealy Machine, Transition-aasigned FSM) 밀리 기계에서는 각 전이에 의해 만들어지는 출력은 그 전이 이전의 내부 상태와, 전이에 사용되는 입력 심벌에 의해 결정됩니다. Mealy 기계는 다음과 같이 정의됩니다. $$ M = (Q, \Sigma, \Delta, \delta, \lambda, q_o)$$ 여기서 Q : 내부 상태들의 유한 집합 Σ : 입력 알파벳(기호)의 집합 Δ : 출력 알파벳(기호)의 집합 δ : 전이 함수, Q x Σ -> Q λ : 출력 함수, Q x Σ -> Δ q0 : 초기 상태 전이 그래프는 유한 인식기에서와 마찬가지..

비결정성은 왜 쓰는가 비결정적 유한 인식기(nfa)는 결정적 유한 인식기(dfa)에 비해 모델링하기 쉬우며, 복잡한 문제를 간략하게 기술하는 데 효과적입니다. 또한 최적해를 찾기 위해 백트래킹(backtraking)등의 기법을 사용하여 모든 경우를 탐색했던 것을 최적의 선택을 할 수 있는 비결정적 알고리즘을 사용한다면 백트래킹 없이 문제를 해결할 수 있으며 결정적 알고리즘은 추가적인 작업을 통해서 비결정성을 시뮬레이트 할 수 있습니다. 이러한 이유로 비결정적 기계는 탐색 - 백트랙 알고리즘에 대한 모델로 사용될 수 있습니다. 또한 비결정성은 몇몇 복잡한 언어들을 간단하게 정의하는 데 효과적입니다. 예를 들어 다음과 같은 생성규칙 $$ S \to aSb | \lambda$$ 은 모든 경우 두 생성규칙들 중..

유한상태 기계(finite state machine) (유한 오토마타) 유한 인식기는 유한 개수의 상태를 가지며, 그 임시 저장장치가 없기 때문에 유한하다고 하며, 문자열을 처리하면서 이를 승인(accept)하거나 거부(reject)하는 기능을 하기 때문에 인식기(accpter)라 합니다. 따라서 유한 인식기를 간단한 패턴 인식 매커니즘이라 볼 수 있습니다. 결정적 유한 인식기 (Deterministic finite accepter, DFA) 결정적이라는 단어의 의미는 해당 오토마타가 항상 하나의 선택만을 취할 수 있음을 의미합니다. DFA는 정규 언어(regular language)라 불리는 특별한 형태의 언어를 정의하기 위해 사용합니다. 결정적 유한 인식기(Deterministic finite acc..

언어 (Languages) 우리들은 이미 자연 언어(natural languages)를 사용하고 있으며, 이러한 개념과는 친숙합니다. 그러나 "언어"라는 단어에 대해서 설명을 하라고 한다면, 이는 생각보다 어려울 것입니다. 언어라는 단어를 검색해보면 사실, 개념들을 표현할 수 있도록 해 주는 심벌(symbol)들의 집합과, 심벌을 다루는 규칙들의 집합을 수반하는 시스템이라 비공식적인 정의를 내리고 있습니다. 심벌(symbol, 기호) 혹은 단말 심벌(terminal symbol) a, b, c, .. 등과 같은 기호들입니다. 알파벳(Alphabet) 알파벳이란 하나 이상의 심벌들의 유한 집합이며, 보통 $\Sigma$로 표현합니다. 문자열(string) 주어진 알파벳에 속한 심벌들을 나열하여 문자열(st..