[계산이론] - (6) 정규 문법(regular grammer)

 

 

정규 언어를 묘사하는 세 번째 방법으로 간단한 문법을 사용하는 방법이 있습니다. 

 

 

우선형 문법과 좌선형 문법

문법 $G = (V, T, S, P)$ 에서 모든 생성규칙들이 다음의 형태를 갖는 경우 이를 우선형(right-linear) 문법이라 합니다.

$$A \to xB$$
$$A \to x   \;\;\;\;\;\; A,B \in V, \;\; x \in T^{*}$$

 

 

또한 문법의 생성규칙들의 다음의 형태를 갖는 경우 이를 좌선형(left-linear) 문법이라 합니다.

$$A \to Bx$$
$$A \to x$$

 

 

정규 문법은 우선형 문법 혹은 좌선형 문법입니다.

 

정규 문법에서는 모든 생성규칙의 우변에 변수(Variable)가 최대 하나까지만 있을 수 있으며,

정규 문법의 모든 생성규칙의 우변에서 변수의 위치는 항상 모두 가장 오른쪽(우선형 문법)에 있거나 가장 왼쪽(좌선형 문법)에 있어야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

선형 문법은 정규 문법이 아니다.

우선형 문법 혹은 좌선형 문법을 정규 문법이라 하였습니다만, 주의해야 할 점이 하나 있습니다.

 

아래와 같은 문법은 정규 문법이 아닙니다.

$$S \to A$$
$$A \to aB \;|\; \lambda$$
$$B \to Ab$$

이는 각 생성규칙들이 우선형 또는 좌선형의 형태를 취하지만, 문법 자체는 좌선형도 아니고 우선형도 아니므로 이는 정규 문법이 아닙니다.

 

위와 같이 각 생성규칙의 우변에 하나 이하의 변수(Variable)만이 있을 수 있으며, 이 변수의 위치에는 제한이 없을 때, 이를 선형 문법이라 부릅니다.

따라서 모든 정규 문법은 선형 문법이 되지만, 모든 선형 문법이 정규 문법이 되지는 않습니다.

 

 

 

 

 

 

 

 

다음으로는 모든 정규 언어에 대해 이에 해당하는 정규 문법이 존재함을 보일 것입니다.

이를 통해 저희는 정규 문법은 정규 언어에 대한 또다른 표현 방법이라는 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

정규문법 $\to$ 유한 오토마타

우선 우선형 언어에 의해 생성되는 언어가 모두 정규 언어임은 다음과 같은 아이디어를 통해 증명할 수 있습니다.

 

우선형 문법의 문장 형태(sentential form)는 그 안에 하나의 변수만이 존재하고,
이 변수가 가장 오른쪽에 나타나는 형태를 가집니다.

 

 

즉 우선형 문법의 생성규칙들을 통해 다음과 같은 유도 과정이 발생함을 예측할 수 있습니다.

$$V_0 \Rightarrow  v_1V_i$$

$$V_0 \Rightarrow  v_1v_2V_j$$

$$V_0 \overset{*}{\Rightarrow} v_1v_2...v_kV_n$$

$$V_0 \Rightarrow  v_1v_2...v_kv_l = w$$

 

 

이때 각각의 Vi들을 nfa의 하나의 상태로 본다면, 쉽게 nfa를 작성할 수 있을 것입니다.

이를 통해 우선형 문법에 의해 생성되는 언어는 모두 이를 인식하는 nfa를 가짐을 알 수 있고, nfa는 그와 동치인 dfa를 가지므로 결국 정규 언어입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

유한 오토마타 $\to$ 정규문법

정규 언어의 정의에 따라 이를 인식하는 dfa가 존재합니다.

 

정규 언어를 L, 이를 인식하는 dfa를 M이라 할 때 우선형 문법 $G=(V, \Sigma, S, P)$ 를 구성하도록 하겠습니다.

M에 속하는 $\delta(A, a) = B$ 와 같은 형태의 각 전이에 대하여, 문법 G는 다음과 같은 생성규칙을 가집니다.
$$A \to aB$$

또한 Final State에 속하는 상태 F에 대하여, 문법 G는 다음 생성규칙을 추가로 가집니다.
$$F \to \lambda$$

예시

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

정규 언어와 정규 문법간의 동치성

언어 L이 정규 언어이고, 그럴 때에만 L = L(G)를 만족하는 정규 문법 G가 존재합니다.

 

 

 

 

 

 

 

 

 

 

정규 언어를 표현하는 세가지 방법

이전 글과 이번 글을 통해 정규 언어를 묘사하는 세가지 방법에 대해서 알아보았습니다.

 

nfa와 dfa, 정규 표현, 정규 문법 모두 정규 언어에 대한 완전하고 모호하지 않은 정의를 제시할 수 있으며,

이들간의 표현 능력은 모두 동일합니다.

 

그리고 이들 사이의 변환 역시 가능하며, 다음과 같은 관계를 가짐을 알 수 있습니다.

 

 

 

 

 

 

 

정규언어와 정규문법

다음 문장들은 같은 의미입니다.

L은 정규집합(regular set)입니다.
L은 좌선형 또는 우선형 언어입니다.
L은 유한 오토마타에 의해 인식되는 언어입니다.
L은 NFA 언어입니다.
L은 정규표현에 의해 나타낼 수 있습니다.

 

 

 

 

 

 

 

정규문법(G3), 정규 표현(RE), 유한 오토마타(FA)간의 변환

지금까지 공부했던 정규 언어를 표현하는 세가지 방법들 사이의 변환에 대해 학습해보도록 하겠습니다.

 

 

 

 

 

정규표현(RE) -> 정규문법(G3)

기본적인 방법은 다음과 같습니다.

 

 

 

 

이를 사용하여 아래 예제들을 풀어보겠습니다.

 

 

 

조금 더 어려운 예제입니다.

 

 

 

 

 

 

 

 

 

 

정규문법(G3) -> 정규표현(RE)

기본적인 방법은 다음과 같습니다.

 

예제는 다음과 같습니다.

 

 

 

 

 

 

 

 

 

 

 

유한 오토마타(FA)->  정규문법(G3)

기본적인 방법은 다음과 같습니다.

 

 

 

예제는 다음과 같습니다.

 

 

 

 

 

 

 

정규문법(G3) -> 유한 오토마타(FA)

기본적인 방법은 다음과 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

정규표현(RE) -> 유한 오토마타(FA)

기본적인 방법은 다음과 같습니다.

 

 

 

 

 

 

 

유한 오토마타(FA) -> 정규표현(RE)

직접 변환하는 것은 매우 어렵고, 지금까지 학습했던 것들을 사용하여 FA -> G3 -> RE순으로 바꾸어 표현합니다.

사실 위 FA -> G3 예제에서 해보았습니다.

 

 

 

 

 

 

 

전체적 변환 예시들

FA 에서 A에서 a가 아니라 0 받으면 A입니다.ㅠㅠ