Grammars 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Regular Languages#Grammars|Regular Languages]]

==개요==
Grammar는 [[Finite Automata|DFA]]나 [[Finite Automata|NFA]]처럼 문자열을 소비하며 “인식(recognize)”하는 것이 아닌, 문자열을 생성(generate) 하는 시스템이다. 즉, grammar는 어떤 언어에 속하는 모든 문자열을 만들어내는 규칙들의 모음이다. 

==Classes of Grammars==
문법은 아래와 같이 네가지로 구분된다:
# Unrestricted Grammar: 아무 제약이 없는 일반적인 형태
# Context-sensitive Grammar: 각 규칙에서 <math>|l| \le |r|</math>이다.
#* 이는 규칙을 적용하는 과정에서 문자열의 길이가 줄어들지 않음을 의미한다.
# Context-free Grammar(CFG): 모든 규칙의 왼쪽이 단 하나의 비단말기라는 것을 의미한다.(<math>l \in V</math>)
#* 문맥과 상관없이 하나의 비단말기만 보고 규칙을 적용할 수 있다.
#* PDA(푸시다운 오토마톤)과 동일한 계산 능력을 가진다.
# Regular Grammar: CFG보다 더욱 단순한 형태이다.
#* 각 규칙은 <math>r = w</math>또는 <math>r = wB</math>꼴이며, 오른쪽 끝에 비단말기가 올 수 있다.
#* 이는 이름에서 짐작할 수 있듯이 정규언어와 정확히 동일한 클래스이다.
이때 Regular Grammar G가 정규언어와 정확히 동일한 클래스라는 것은 아래와 같은 의미이다:
 L is regular 
 <math>\Leftrightarrow L=L(G)</math> for some regular grammar G
즉, 정규 언어와 정규 문법으로 생성 가능한 언어는 동일한 집합을 의미한다.

==Definition of Grammars==
Grammar는 아래와 같은 4-튜플(<math>V,\Sigma, R, S</math>)을 통해서 정의된다:
# <math>V</math>: 비단말기(nonterminal symbols)의 유한 집합
#* 예: <math>\{S, A, B\}</math>
#* 실제 문자열에 직접 등장하지는 않지만, 생성 과정에서 사용된다.
# <math>\Sigma</math>: 단말기(terminal symbols) 의 유한 집합
#* 예: <math>\{a,b,0,1\}</math>
#* 실제 언어의 문자열을 구성하는 기호들이며, <math>V</math>와 겹치지 않는다.
# <math>R</math>: 규칙(rule)의 유한 집합
#* 각 규칙은 <math>l\rightarrow r</math> 형태이고, <math>l, r \in (V \cup \Sigma)*</math>
#* <math>l</math>은 최소 하나의 비단말을 포함해야 하며, 규칙은 단말을 단말이나 다른 비단말로 치환하는 역할을 한다.
# <math>S \in V</math>: 시작 기호(start symbol)
이때 두 집합 <math>V, \Sigma</math>의 모든 기호를 섞어서 만들 수 있는 문자열 전체는 <math>(V\cup \Sigma)*</math>이다. 이는 sentential form이라고 불리며, 문법(Grammar)으로 문자열을 생성하는 과정에서 만들어지는 모든 문자열을 의미한다. 

===Derivations===
문법을 사용해서 문자열을 생성하는 과정(derivation)은 아래와 같다:
* <math>u \Rightarrow v</math>: “u가 v를 한 단계 유도한다.”
** 즉, 어떤 규칙 <math>l \rightarrow r</math>을 적용하여<br><math>u=w_1lw_2</math>인 문자열에서 <math>l</math>을 <math>r</math>로 바꾸면 <math>v = w_1rw_2</math>가 된다.
** 즉, <math>u</math> 안의 한 비단말기를 규칙에 따라 다른 형태로 치환하여 <math>v</math>를 얻는 것이다.
또한, 주어진 규칙 내에서 여러번 규칙을 적용하여 문자열 <math>v</math>를 얻을 수 있는데, 이를 기호로 나타내면 <math>u \Rightarrow* v</math>이다. 예를 들어, <math>u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow \cdots \Rightarrow v</math>와 같은 방식이다. 이를 통해 문법 G가 생성하는 언어 <math>L(G)</math>는 아래와 같이 정의된다:
 <math>L(G) = \{w \in \Sigma*|S \Rightarrow* w\}</math>

===Derivations Example 1===
예를 들어, 아래와 같은 CFG <math>G = (V, \Sigma, R, S)</math>가 주어졌다고 가정하자:
* <math>V =\{S\}</math>
* <math>\Sigma = \{0,1\}</math>
* <math>R = \{S\rightarrow \epsilon, S \rightarrow 0S1\}</math>
위와 같은 grammar에서 문자열은 아래와 같이 유도된다:
 <math>S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S1111 \Rightarrow 000111</math>
즉, 같은 개수의 0과 1로 이루어진 문자열을 만들며, 이를 수식으로 표현하면 아래와 같다:
 <math>L(G) = \{0^n1^n|n\ge 0\}</math>

===Derivations Example 2===
아래는 수학식(expression)을 생성하는 CFG <math>G = (V, \Sigma, R, S)</math>이다:
* <math>V =\{E, T, F\}</math>
* <math>\Sigma = \{a, +, \times, (, )\}</math>
* <math>R = \{E \rightarrow E + T|T, T\rightarrow T\times F|F, F \rightarrow (E)|a\}</math>
위 문법은 수학적인 식을 계층적으로 정의한다:
* E (식)은 하나 이상의 항(T)의 덧셈으로 이루어짐
* T(항)은 하나 이상의 인자(F)의 곱셈으로 이루어짐
*F(인자)는 괄호친 식(E) 이거나 단일 변수 a
아래는 위의 산술식 문법을 실제로 적용하여 <math>a+(a\times a)</math> 문자열을 생성하는 예시이다:
 <math>E \Rightarrow E + T \Rightarrow E + F \Rightarrow E + (E) \Rightarrow T + (E) \Rightarrow F + (E)</math>
 <math>\,\,\, \Rightarrow F + (T) \Rightarrow F + (T \times F) \Rightarrow F + (F \times F) \Rightarrow F + (a \times F)</math>
 <math>\,\,\, \Rightarrow F + (a \times a) \Rightarrow a + (a \times a)</math>
즉, 이 문법은 괄호, 곱셈, 덧셈을 포함한 올바른 산술식을 생성할 수 있다.

===Leftmost Derivations===
위의 예시들을 예리하게 살펴본다면, 하나의 문자열 <math>w</math> 여러 가지 유도 방법(derivations)을 가지고 생성할 수 있다는 것을 알 수 있다. 따라서 이러한 이런 “유도 순서의 차이”로 생기는 혼란을 없애기 위해, 항상 왼쪽에 있는 비단말기부터 확장하는 규칙을 사용하며, 이를 leftmost derivation(좌측 유도)이라고 한다.

예를 들어, 아래는 위의 산술식을 생성하는 grammar를 leftmost derivation을 사용하여 문자열 <math>a + (a \times a)</math>를 유도한 것이다:
 <math>E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow a + F \Rightarrow a + (E)</math>
 <math>\,\,\, \Rightarrow a + (T) \Rightarrow a + (T \times F) \Rightarrow a + (F \times F) \Rightarrow F + (a \times F)</math>
 <math>\,\,\, \Rightarrow a + (a \times F) \Rightarrow a + (a \times a)</math>

===Parse Trees===
Parse Trees는 유도 과정을 트리(tree) 형태로 표현한 것이다. CFG에 대한 parse tree는 아래와 같은 특징을 가진다:
# CFG에 대한 parse tree는 ordered tree이다.
# Internal nodes는 비단말기이다.
# Leaf nodes들은 단말기이다.
# 각 internal nodes는 문법의 규칙 <math>A \rightarrow r</math>에 따라 자식 노드를 가지며, 자식 노드의 수는 <math>|r|</math>과 같다.
[[파일:Figure 1. Parse Trees Example 1.png|섬네일|168x168픽셀|Figure 1. Parse Trees Example 1]]
예를 들어  CFG <math>G = (V, \Sigma, R, S)</math>가 아래와 같이 주어졌다고 가정하자.
* <math>V =\{S, E\}</math>
* <math>\Sigma = \{a, -\}</math>
* <math>R = \{S \rightarrow E, E\rightarrow E-E, E \rightarrow a\}</math>
위와 같은 grammar에 대해 문자열 <math>a-a-a</math>를 유도하는 parse tree는 figure 1과 같다. 이때 하나의 leftmost derivation은 하나의 parse tree와 정확히 1:1로 대응한다. Figure 1에 나타난 유도과정은 아래와 같은 leftmost derivation과 대응된다:
 <math>S \Rightarrow E \Rightarrow E - E \Rightarrow a -E </math>
 <math>\,\,\, \Rightarrow a-E-E\Rightarrow a-a-E\Rightarrow a-a-a</math>
[[파일:Figure 2. Parse Trees Example 2.png|섬네일|Figure 2. Parse Trees Example 2]]
Figure 2는 다르게 parse tree가 구성되었다면, 이와 대응되는 leftmost derivation또한 달라진다는 것을 보여준다.

===Ambiguity===
하나의 문자열을 생성할 때, 여러 개의 트리로 표현될 수 있다면 해당 문법은 “모호하다(ambiguous)”고 한다. 예를 들어, figure 2에 주어진 서로 다른 트리는 같은 문법을 통해 같은 문자열 <math>a-a-a</math>를 서로 다른 순서를 통해 유도하는 것을 보여준다. 따라서 해당 문법은 모호하다.

==Context-Free Languages==
CFL(Context-Free Languages)이란 어떤 CFG로부터 생성될 수 있는 언어이다. 이는 아래와 같이 나타내어 진다:
 A language L is context-free 
 <math>\Leftrightarrow L=L(G)</math> for some CFG G
이때 모든 정규언어는 context-free이다. 이는 모든 정규 언어는 항상 regular grammar로 표현될 수 있는데, 모든 정규 문법은 문맥자유문법의 특수한 형태이기 때문이다. 즉, 아래와 같은 명제가 성립한다.
 Regular Languages <math>\subseteq</math> Context-Free Languages
이는 정규언어보다 CFL의 표현력이 더 강하다는 것을 의미한다. 예를 들어 <math>L=\{0^n1^n|n\ge 0\}</math>과 같은 언어는 정규언어가 아니지만 CFG로는 표현 가능하다. 또한 아래와 같은 명제가 성립한다:
 The class of context-free languages is closed under <math>\cup, \circ, *</math>.
이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.

===Chomsky Normal Form===
CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다:
# <math>A \rightarrow BC</math><ref>이때 B, C는 시작 기호 S가 아니다</ref>
# <math>A \rightarrow a</math>
# <math>S \rightarrow \epsilon</math>
CFG를 CNF로 바꾸더라도 새로운 문자열이 생성되지는 않으며, 모든 grammar와 문자열이 그대로 보존된다. 아래와 같이 CFG가 주어졌다고 가정하자:
 <math>S \rightarrow ASA | aB</math>
 <math>A \rightarrow B | S</math>
 <math>B \rightarrow b | \epsilon</math>
CNF에서는 시작기호가 우변에 등장하면 안 되므로, 기존 시작기호 <math>S</math>를 포함하는 새 시작기호 <math>S_0</math>를 만든다. 이를 통해 모든 변환은 <math>S_0</math>에서 시작한다. 이를 통해 아래와 같은 식을 추가한다:
 <math>S_0 \rightarrow S</math>
또한 주어진 식에 <math>B \rightarrow \epsilon</math>이 존재하므로 제거해야 한다. 이를 위해서 <math>B\rightarrow \epsilon</math> 규칙을 제거하고, <math>B</math>를 포함하는 식이 유도되는 모든 규칙에서, <math>B</math>를 <math>\epsilon</math>으로 치환한 아래의 식을 추가한다:
 <math>S \rightarrow aB \rightarrow a</math>
 <math>A \rightarrow B \rightarrow \epsilon</math>
위와 같은 과정을 <math>A \rightarrow \epsilon</math> 규칙에 대해서도 동일하게 적용해야 한다. 이를 위해 해당 식을 제거하고, 아래의 식들을 추가한다:
 <math>S \rightarrow S</math>
 <math>S \rightarrow AS</math>
 <math>S \rightarrow SA</math>
또한, <math>A \rightarrow S, A \rightarrow B, S \rightarrow</math>와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:
 <math>S \rightarrow ASA|SA|AS|aB|a</math>
 <math>B \rightarrow b</math>
 <math>S_0 \rightarrow ASA|SA|AS|aB|a</math> <ref><math>S_0 \rightarrow S</math> 규칙을 삭제하며 추가</ref>
 <math>A \rightarrow ASA|SA|AS|aB|a</math> <ref><math>A \rightarrow S</math> 규칙을 삭제하며 추가</ref>
 <math>A \rightarrow b</math> <ref><math>A \rightarrow B</math> 규칙을 삭제하며 추가</ref>

이제, CNF에서는 규칙의 오른쪽에 두개의 비단말만 가능하므로 3개 변수인 <math>ASA</math> 형태를 분해해야 한다. 이를 위해 해당 규칙을 아래와 같이 중간 비단말 <math>S_1, A_1</math>을 활용한 규칙들로 대체해야 한다.<ref>S_1, A_1과 같이 굳이 변수를 두개 추가하는 이유는 S에서 파생된 규칙과 A에서 파생된 규칙을 구분하기 위해서이다.</ref>:
 <math>S \rightarrow AS_1</math>
 <math>S_1 \rightarrow SA</math>
 <math>A \rightarrow AA_1</math>
 <math>A_1 \rightarrow SA</math>
또한, CNF에서는 단말이 반드시 단독으로만 나와야 하므로, <math>S \rightarrow aB</math>와 같은 규칙은 허용되지 않는다. 따라서 해당 규칙을 아래와 같이 중간 비단말 <math>A_2</math>을 활용한 규칙들로 대체해야 한다:
 <math>A_2 \rightarrow a</math>
 <math>S \rightarrow A_2B</math>
따라서 아래와 같이 최종적인 CNF가 도출된다:
 <math>S \rightarrow AS_1|SA|AS|A_2B|a</math>
 <math>B \rightarrow b</math>
 <math>S_0 \rightarrow AS_1|SA|AS|A_2B|a</math>
 <math>A \rightarrow AA_1|SA|AS|A_2B|a</math> 
 <math>A \rightarrow b</math> 
 <math>A_2 \rightarrow a</math>

==각주==