Leftmost / Rightmost Derivation다시 복습해보면 Derivation(유도)는 문법으로부터 문장을 만드는 과정에 등장하는 Sentential Form 또는 Sentence를 말한다.이때 어떤 프로덕션이 S → ABC 이고, A, B, C 는 변수라고 해보자.A, B, C가 produce하는 결과물을 각각 a, b, c 라고 할 때, S에서 시작해서 문장을 만드는 과정의 선택지는 여러가지가 있을 수 있다. S => aBC => abC => abc 가 될 수도 있고,S => AbC => Abc => abc 가 될 수도 있다. 따라서 같은 문장을 유도하는 과정이 여러가지 인 경우에는 각 단계에서 어떤 것을 선택해야 할 지 고려해야 할 점이 많다보니 상대적으로 비효율적이라, 일관된 기준을..
Context-Free LanguageL = { aⁿbⁿ : n ≥ 0 } 위 언어는 펌핑 레마를 통해 RL이 아님을 증명한 적이 있다.그런데 이 언어는 프로그래밍 언어에서 등장하는 언어로 표현할 수 있다.homomorphism을 이용하여 h(a) = '(', h(b) = ')' 로 표현하면 위 언어는 언제나 올바른 괄호 문자열이 된다.(강의록에서는 nested programming language 라고 표현하였다.) 그런데 우리는 분명 이런 언어도 표현하기를 원할 때가 있다.따라서 RL 보다 더 넓은 범위를 커버할 수 있는 언어를 새로 정의해보려고 한다. 그리고 그 시작으로 Context-Free Language를 먼저 정의해보자. Def. 만약 G = (V, T, S, P) 를 구성하는 모든 prod..
위와 같은 언어 L을 DFA로 표현해보자.주어진 언어는 aa를 포함하는 임의의 a, b로 구성된 문자열을 문장으로 갖는다. 정규표현식과 DFA 로는 위와 같이 표현할 수 있다.충분히 어렵지 않다. 위 언어는 regular expression 으로 표현할 수 있고, 또는 DFA로 나타낼 수 있었으므로 Regual Language 이다. 이제 이 DFA를 파이썬 코드로 작성해보자. DFA의 트랜지션 함수는 위와 같다. DFA 함수를 위와 같이 정의한다.s 라는 전체 문장에서 심볼을 하나씩 읽으면서 현재 상태에서 이 심볼을 읽었을 때 그 다음 state를 transition map을 통해 결정한다.전체 심볼을 다 읽었을 때 최종 state가 final state에 속하면 Accepted 이고, 아니라면 ..
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..
