Regular Language 의 특성 판별 어떤 regular language 에 임의의 문자열을 넣었을 때, 그 문장이 L에 포함되는지 안되는지 결정할 수 있는 알고리즘이 존재한다. 너무나도 당연한 말이다.왜냐하면 regular language 는 DFA를 통해 나타낼 수 있고, 이 기계에 문자열 w를 넣으면 이 문장이 L 에 속하는지 판별할 수 있기 때문이다. DFA는 곧 판별 알고리즘을 나타내는 것과 같으며, 이런 알고리즘을 가리켜 membership algorithm 이라고 한다. standard representation 으로 나타낸 regular language 에 대해서, 이 언어 집합이 공집합, 유한집합, 무한집합 중 어떤 것에 해당하는지 판별하는 알고리즘이 존재한다. 1. 공집합 여부..
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..
NFANondeterministic Finite Accepter DFA와 마찬가지로 유한한 저장공간을 가지며, 답을 yes / no 로만 내는 기계를 말한다.다만 Nondeterministic 이므로, 현재 상태에서 특정 인풋이 주어졌을 때, 다른 상태로 넘어갈 수 있는 길이 여러개가 있거나 없을 수 있는 기계를 말한다. 구성요소 자체는 DFA와 동일하므로 DFA와 유사하게 정의된다. 이때 𝜹 에 들어갈 수 있는 transition function는 DFA와 다르다.델타에는 DFA와 마찬가지로 𝜹(Qx, a) = Qy 로 표기할 수 있다.다만 이때 Qy가 하나의 상태가 아니라 여러 개의 상태 집합일 수 있으며, 입력 심볼에도 빈 문자열 람다가 들어올 수 있다. 위 정의에서 말하는 2^Q 는 pow..
DFA지난 글에서 오토마톤에 대해 정리하면서 오토마톤은 다양한 기준으로 분류할 수 있다고 하였다.그 중에서 이번 글에는 DFA 오토마톤에 대해 정리해보려고 한다. DFA (Deterministic Finite Accepter)는 지난 내용에 따라 다음과 같이 이해할 수 있다. - 결정적이며 (Deterministic, 각 상태에서 주어진 입력에 대해 갈 수 있는 경로가 유일하다.)- 유한한 (Finite, 메모리 == 저장공간이 유한하다.)- Accepter (기계의 output 이 yes(accept) / no(reject) 로 이진적이다.) DFA는 오토마톤의 일종이지만, 특이하게 temporary storage 가 없다.그렇다고 저장공간이 없는 것은 아니고, control unit 에 마치 플립플..
오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.디지털 컴퓨터는 기본적으로 입력이 주어지면 저장공간을 활용하여 이를 적절히 처리한 뒤 결과물을 내보낸다. 이때 입력 데이터는 수학적 편의를 위해서 '알파벳 심볼에 의해 정의된 문자열' 이라고 정의한다. (꼭 이래야만 하는 것은 아니다)그리고 인풋 파일은 무한한 길이의 테이프로부터 문자열을 읽어들일 수 있다고 생각한다.이 테이프는 여러개의 셀로 구성되어 있으며, 각 셀에는 알파벳 심볼 하나가 저장된다. 디지털 컴퓨터는 내부적으로 연속된 시간이 아니라, 이산적인 시간 체계로 동작하며,각 시간마다 인풋 파일의 왼쪽에서 오른쪽을 향해 한번에 하나의 셀(심볼)을 읽어들인다.그리고 End-Of-File (EOF) 신호를 통해 문자열의 끝을 감지할 수 있도록 기계가 ..
Language우리가 사용하는 자연어나 프로그래밍 언어에는 공통점이 있지만, 이를 명확하게 규정하는 것이 쉽지 않다.따라서 우리가 사용하는 언어를 더 쉽고 엄밀하게 다루기 위해서, 언어를 수학을 통해 추상화 해보려고 한다.그리고 이렇게 추상화된 언어를 Formal Language 라고 한다. alphabet 알파벳 ∑ = symbols 로 구성된 공집합이 아닌 유한집합 ∑ = {a, b} => 이 알파벳을 사용하여 만드는 언어는 a, b 로만 구성될 수 있다.∑ = {0, 1} => 이 알파벳을 사용하여 만드는 언어는 0, 1 로만 구성될 수 있다. String유한한 길이를 갖는 symbols의 나열 (무한히 나열한 것은 아니다.)위 예시에서의 알파벳을 사용하여 문자열을 구성한다면 다음과 같은 문자열을 ..
