Grammars

상위 문서: Regular Languages

개요

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

Definition of Grammars

Grammar는 아래와 같은 4-튜플($V,\mathrm{\Sigma },R,S$)을 통해서 정의된다:

1. $V$: 비단말기(nonterminal symbols)의 유한 집합
   • 예: $\{S,A,B\}$
   • 실제 문자열에 직접 등장하지는 않지만, 생성 과정에서 사용된다.
2. $\mathrm{\Sigma }$: 단말기(terminal symbols) 의 유한 집합
   • 예: $\{a,b,0,1\}$
   • 실제 언어의 문자열을 구성하는 기호들이며, $V$와 겹치지 않는다.
3. $R$: 규칙(rule)의 유한 집합
   • 각 규칙은 $l\to r$ 형태이고, $l,r\in (V\cup \mathrm{\Sigma })*$
   • $l$은 최소 하나의 비단말을 포함해야 하며, 규칙은 단말을 단말이나 다른 비단말로 치환하는 역할을 한다.
4. $S\in V$: 시작 기호(start symbol)

이때 두 집합 $V,\mathrm{\Sigma }$의 모든 기호를 섞어서 만들 수 있는 문자열 전체는 $(V\cup \mathrm{\Sigma })*$이다. 이는 sentential form이라고 불리며, 문법(Grammar)으로 문자열을 생성하는 과정에서 만들어지는 모든 문자열을 의미한다.

Derivations

문법을 사용해서 문자열을 생성하는 과정(derivation)은 아래와 같다:

• $u\Rightarrow v$: “u가 v를 한 단계 유도한다.”
  • 즉, 어떤 규칙 $l\to r$을 적용하여
    $u=w_{1}l{w}_2$인 문자열에서 $l$을 $r$로 바꾸면 $v=w_{1}r{w}_2$가 된다.
  • 즉, $u$ 안의 한 비단말기를 규칙에 따라 다른 형태로 치환하여 $v$를 얻는 것이다.

또한, 주어진 규칙 내에서 여러번 규칙을 적용하여 문자열 $v$를 얻을 수 있는데, 이를 기호로 나타내면 $u\Rightarrow *v$이다. 예를 들어, $u\Rightarrow u_1\Rightarrow u_2\Rightarrow \cdots \Rightarrow v$와 같은 방식이다. 이를 통해 문법 G가 생성하는 언어 $L(G)$는 아래와 같이 정의된다:

$L(G)=\{w\in \mathrm{\Sigma }*|S\Rightarrow *w\}$

Derivations Example 1

예를 들어, 아래와 같은 CFG $G=(V,\mathrm{\Sigma },R,S)$가 주어졌다고 가정하자:

• $V=\{S\}$
• $\mathrm{\Sigma }=\{0,1\}$
• $R=\{S\to ϵ,S\to 0S1\}$

위와 같은 grammar에서 문자열은 아래와 같이 유도된다:

$S\Rightarrow 0S1\Rightarrow 00S11\Rightarrow 000S1111\Rightarrow 000111$

즉, 같은 개수의 0과 1로 이루어진 문자열을 만들며, 이를 수식으로 표현하면 아래와 같다:

$L(G)=\{0^n{1}^n|n\ge 0\}$

Derivations Example 2

아래는 수학식(expression)을 생성하는 CFG $G=(V,\mathrm{\Sigma },R,S)$이다:

• $V=\{E,T,F\}$
• $\mathrm{\Sigma }=\{a,+,\times ,(,)\}$
• $R=\{E\to E+T|T,T\to T\times F|F,F\to (E)|a\}$

위 문법은 수학적인 식을 계층적으로 정의한다:

• E (식)은 하나 이상의 항(T)의 덧셈으로 이루어짐
• T(항)은 하나 이상의 인자(F)의 곱셈으로 이루어짐
• F(인자)는 괄호친 식(E) 이거나 단일 변수 a

아래는 위의 산술식 문법을 실제로 적용하여 $a+(a\times a)$ 문자열을 생성하는 예시이다:

$E\Rightarrow E+T\Rightarrow E+F\Rightarrow E+(E)\Rightarrow T+(E)\Rightarrow F+(E)$
$\Rightarrow F+(T)\Rightarrow F+(T\times F)\Rightarrow F+(F\times F)\Rightarrow F+(a\times F)$
$\Rightarrow F+(a\times a)\Rightarrow a+(a\times a)$

즉, 이 문법은 괄호, 곱셈, 덧셈을 포함한 올바른 산술식을 생성할 수 있다.

Classes of Grammars

문법은 아래와 같이 네가지로 구분된다:

1. Unrestricted Grammar: 아무 제약이 없는 일반적인 형태
2. Context-sensitive Grammar: 각 규칙에서 $|l|\le |r|$이다.
   • 이는 규칙을 적용하는 과정에서 문자열의 길이가 줄어들지 않음을 의미한다.
3. Context-free Grammar(CFG): 모든 규칙의 왼쪽이 단 하나의 비단말기라는 것을 의미한다.($l\in V$)
   • 문맥과 상관없이 하나의 비단말기만 보고 규칙을 적용할 수 있다.
   • PDA(푸시다운 오토마톤)과 동일한 계산 능력을 가진다.
4. Regular Grammar: CFG보다 더욱 단순한 형태이다.
   • 각 규칙은 $r=w$또는 $r=wB$꼴이며, 오른쪽 끝에 비단말기가 올 수 있다.
   • 이는 이름에서 짐작할 수 있듯이 정규언어와 정확히 동일한 클래스이다.

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$