[계산이론] - (8) 비정규 언어의 식별

 

 

 

비정규 언어의 식별

정규 언어는 무한 집합일 수 있습니다.

그러나 정규 언어는 정의에 따라 유한 오토마타에 의해 인식이 되며, 이는 정규 언어의 구조에 어떠한 제약을 부여하며, 따라서 어떤 언어가 정규 언어가 되기 위해서는 이러한 제약을 따라야 합니다.

 

 

저희는 주어진 언어에 대하여 이것이 정규 언어가 아님을 증명하는 방법들을 배울 것입니다.

다음과 같은 방법이 있습니다.

비둘기집 원리

펌핑 보조정리 (pumping lemma)

 

 

 

 

 

 

비둘기집 원리 (피전홀 원리)

비둘기집의 개수를 m,
비둘기의 수를 n이라 하였을 때,
m < n 인 경우 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어가 한다는 원리입니다.

 

비둘기집 원리를 이용하여 다음 언어가 정규 언어인지 아닌지 확인해보도록 하겠습니다.

$$L = \left\{  a^{n}b^{n} \;:\; n  \geq  0  \right\}$$

 

 

L이 정규 언어라고 가정해보겠습니다.

그러면 L을 인식하는 dfa가 존재합니다. dfa M를 다음과 같이 정의하겠습니다.

$$M = (Q, \left\{ a,b  \right\} , \delta, q_0, F)$$

 

모든 i = 1, 2, 3, ... 에 대하여, 다음과 같은 확장 전이함수를 살펴보겠습니다.

$$\delta^{*} (q_0, a^{i})$$

 

여기서 i의 개수는 무한개인 반면, M의 상태들의 개수는 유한개입니다.

무한은 유한보다 큽니다.

 

 

 

피전홀 원리에 의해 상태들의 개수보다 a의 개수가 많으므로,

다음의 조건을 만족하는 상태 q가 존재하여야 합니다.

$$\delta^{*} (q_0, a^n) = q$$
$$\delta^{*} (q_0, a^m) = q$$
$$단 \; n \neq m$$

 

 

저희는 L을 정규 언어라 가정했기에, 위 조건을 만족하는 상태 q에 대하여 다음이 성립해야 합니다.

$$\delta^{*} (q, b^n) = q_f \in F$$

 

 

이를 통해 다음이 유도됩니다.

$$\delta^{*}(q_0, a^{m}b^{n}) = \delta^{*}(\delta^{*}(q_0, a^{m}), \; b^{n})$$
$$=\delta^{*}(q, b^{n})$$
$$=q_f$$

 

위를 통해 n과 m이 다른 문법에 대해서도 dfa M이 승인하므로, L이 정규 언어라는 가정에 모순됩니다.

따라서 L은 정규 언어가 될 수 없습니다.

 

 

 

 

참고

증명의 중간 과정에서 이해가 어려운 부분이 있을 수도 있을 거 같아 참고자료를 추가하겠습니다.

다음 부분입니다.

피전홀 원리에 의해 다음의 조건을 만족하는 상태 q가 존재하여야 합니다.
$$\delta^{*} (q_0, a^n) = q$$
$$\delta^{*} (q_0, a^m) = q$$
$$단 \; n \neq m$$

 

 

 

 

 

 

 

 

정규 언어의 전이 그래프에 대한 성질

어떠한 언어가 정규 언어인지 아닌지를 판별할 때, 다음 성질들을 이용할 수 있습니다.

1. 전이 그래프가 사이클을 가지지 않으면 해당 언어는 유한합니다.
어떠한 언어가 유한하다면 해당 언어는 정규 언어입니다.

2. 전이 그래프가 비어있지 않은 라벨(즉 람다 전이가 아닌)이 포함된 사이클을 가지면 해당 언어는 무한 정규 언어입니다.

3. 사이클이 있을 경우 이 사이클은 생략될 수도 있고, 임의의 횟수만큼 반복될 수도 있습니다. 
사이클이 라벨 v를 가지면서, 문자열 wvw가 해당 언어에 속할 경우, ww와 wvvw, wvvvw등도 해당 언어에 속합니다.

4. 주어진 dfa의 어느 부분에 이러한 사이클이 존재하는지는 알 수 없습니다.
다만 그 dfa가 m개의 상태를 가진다면 m개의 심벌이 읽혀지는 시점에 사이클이 시작됩니다.

 

어떠한 언어 L에 대하여, 이러한 성질을 가지지 않는 문자열 w가 하나라도 있다면, 그 언어 L은 정규 언어일 수 없습니다.

 

이러한 관찰을 통해서 펌핑 보조정리를 언급할 수 있습니다.

펌핑 보조정리는 조금 어렵기에 다음 글에 이어서 다뤄보도록 하겠습니다.