[계산이론] - (13) 정규형(Chomwky 정규형, Greibach 정규형)

 

 

 

Chomsky 정규형

Chomsky 정규형은 생성규칙의 우변에 있는 심벌들의 수를 2개 이하로 엄격하게 제한한 형태입니다.

문맥 자유 문법 G에서 모든 생성규칙이 다음의 형태를 만족하면 G를 Chomsky 정규형이라 합니다.

$$A \to BC$$
혹은 
$$A \to a$$

단 여기서 A, B, C ∈ V 이고 a ∈ T 입니다.

 

 

아래는 Chomsky 정규형의 예시입니다.

$$S \to AS \;|\;a$$
$$A \to SA \;|\;b$$

 

아래는 Chomsky 정규형이 아닙니다.

$$S \to AS \;|\;AAS$$
$$A \to SA \;|\;bb$$

 

 

 

 

 

 

 

 

 

 

 

 

Chomsky 정규형으로 변환하기

 

주어진 문법 G는 람다 생성규칙과, 단위 생성규칙을 가지고 있지 않아야합니다.
(가지고 있는 경우 이를 제거한 뒤 변환합니다.)

1. 주어진 문법 G에 대하여 ,G의 생성규칙들 중에서 다음 형태를 만족하는 모든 생성규칙들을 고려하면서, G를 G1= (V1, T, S, P1)으로 변환합니다.
$$A \to x_1 x_2 ... x_n$$
여기서 각 xi는 V 또는 T에 속한 심벌입니다.
만약 n=1인 경우에는  단위-생성규칙을 갖지 않기에 x1은 단말 심벌(terminal symbol)이어야 합니다.
이 경우에 해당 생성규칙을 P1에 포함시켜야 합니다.


그러나 만약 n이 2 이상인 경우에는 T에 속한 모든 단말 심벌 a에 대해서, 새로운 변수 Ba를 도입합니다.
(a로 고정된 것이 아니라, b인 경우 Bb, c인 경우 Bc인 식입니다.)


n이 2 이상인 경우 위 식의 형태를 만족하는 P의 모든 생성규칙에 대해서, 다음의 생성규칙을 P1에 포함시킵니다.
$$A \to C_1C_2...C_n$$

단 여기서 만약 xi가 V에 속하는 경우 Ci=xi이며,
xi=a(terminal symbol)인 경우에는 Ci = Ba입니다.


각 변수 Ba에 대하여, P1에 다음의 생성규칙을 포함시킵니다.
$$B_a \to a$$

위의 과정은 길이가 2 이상인 생성규칙들에 있는 모든 단말 심벌들을 새로이 도입한 변수들로 치환하여, 단말 심벌들을 제거합니다.
이 단계를 모두 마치고 나면 다음 형태를 만족하는 생성규칙들로만 된 문법 G1이 생성됩니다.
$$A \to a$$
혹은
$$ A \to C_1C_2 ... C_n$$

 

 

 

2. 다음으로는 생성규칙의 우변에 있는 문자열의 길이를 필요에 따라 줄이기 위하여 새로운 변수들을 도입합니다.
우선 다음 두 형태의 모든 생성규칙들을 모두 P^에 포함시킵니다.
$$A \to a$$
$$A \to C_1C_2 \;\;\;\;\;오직 \;길이가\; 2여야\; 함$$
이후 길이가 2 이상인 경우에는 새로운 변수들 D1, ..., Dn을 생성하여 다음 생성규칙들을 P^에 포함합니다.
$$A \to C_1D_1$$
$$D_1 \to C_2D_2$$
...
$$D_{n-2} \to C_{n-1}C_{n}$$


이렇게 정의된 P^을 생성규칙으로 가지는 문법 G^는 명백히 Chomsky 정규형입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Greibach 정규형

Greibach 정규형은 생성규칙의 우측에 있는 문자열의 길이에는 제한을 두지 않는 대신에,

변수와 단말 심벌들이 나타나는 위치에 대하여 제한을 둡니다.

문맥-자유 문법 G에서 모든 생성규칙이 다음의 형태를 만족하면 G를 Greibach 정규형이라 합니다.
$$A \to ax$$
단 여기서  a ∈ T이고, x ∈ V* 입니다.

 

위의 정의를 보면 Greibach 정규형과 단순 문법(S-문법)은 차이가 없어 보이지만, 중요한 차이점이 하나 있습니다.

Greibach 정규형에는 쌍(A, a)가 많아야 한 번만 나타나야 한다는 제한이 없습니다.

 

 

지금까지 언급하였던 기법들을 사용하여 주어진 모든 문맥-자유 문법을 Greibach 정규형으로 바꿀 수 있습니다.

이는 증명이 매우 까다롭고, 이후 배울 내용을 단순하게 하기 위해서만 사용되므로 이에 대한 증명은 하지 않고 사용하겠습니다.