Nonregular Languages

유한 기계가 할 수 없는 일들에 대해서 알아보자.

Nonregular Languages

• 우리는 유한 기계(Finite automata)가 할 수 있는 일에 대해서 지금까지 배워왔다. Finite automata가 하는 일을 제대로 이해하려면, 하지 못하는 일에 대한 이해도 필수적으로 필요하다.
• 어떤 language는 finite automaton으로 나타낼 수 없다.
• 예를 들면 $B = \{0^n1^n | n ≥ 0\}$은, finite automaton으로 나타낼 수 없다.
  • n을 특정한 값으로 지정하는 순간 모델은 정해지는데, 그 이상의 값을 나타낸다는 보장이 없다.
  • 다른 말로 하면 0의 개수를 알아야 모델을 그릴 수 있다.
  • 그러나 0의 개수를 나타내는 n은 개수 제한이 없으므로 무한한 가능성이 있다.
  • 이것은 유한 기계(Finite automata)에서는 불가능하다.
• 어떤 language를 특정한 finite automata가 recognize하는지 알 수 있는 방법은 Pumping Lemma를 이용한다.

The Pumping Lemma for Regular Languages

• Pumping Lemma는 모든 regular language에 대해서 만족하고, regular language가 아니면 Pumping Lemma를 만족하지 않는다.
• 우리는 이를 귀류법을 이용해서 증명할 것이다.
• B = $\{0^n1^n | n ≥ 0\}$가 regular language라고 가정해보자.
• B는 pumping lemma를 만족해야 한다. 만약 만족하지 않으면 B는 regular language가 아니다.
• Pumping Lemma는 p가 존재해서, p보다 긴 모든 string s의 어떤 xyz는 다음을 만족해야한다.

  1. 모든 $i ≥ 0$에 대해서, $s' = xy^iz ∈ A$
  2. $|y| > 0$
  3. $|xy| ≤ p$

• 위의 말이 참이 아니려면, 어떤 string s 의 모든 xyz는 하나라도 만족하면 된다.
• 이러한 s를 찾았으면, 귀류법에 따라서 B는 regular language가 아니다.

Example

B = $\{0^n1^n | n ≥ 0\}$가 R.L이라 가정한다.
-> B는 P.L를 만족한다.
-> p라는 P.L가 존재한다
-> $|S|≥p$ 인 s가 존재한다. 여기서는 예시로 $0^p1^p$를 들었다.
-> $|0^p1^p|≥p$이므로 $|S|≥p$다.
-> $S = 000000...111111...$
-> 이런 S를 xyz로 나누는 방법은 매우 많다. 여기서는 y를 집중해서 나누었다. y는 3가지 경우가 있을 수 있다.

• y 안에는 0만 있다 : 그렇다면 y는 적어도 1개 이상의 0을 가지고 있다. s' = xyyz일 때 0의 개수는 늘어나지만, 1의 개수는 그대로이므로 0과 1 모두 p일순 없다(둘의 개수가 다르므로). 그러므로 y 안에 0만 있을 순 없다.
• y 안에는 1만 있다. : 그렇다면 y는 적어도 1개 이상의 1을 가지고 있다. s' = xyyz일 때 1의 개수는 늘어나지만, 0의 개수는 그대로이므로 0과 1 모두 p일순 없다(둘의 개수가 다르므로). 그러므로 y 안에 1만 있을 순 없다.
• y 안에 0에서 1로 바뀌는 순간이 있다. : 그렇다면 xyyz는 0과 1의 개수는 같을 수 있지만, 패턴이 달라진다. 예를 들어 y = 01일때, 000...0101...111이 되므로 0이 다 나오고 1이 나와야하는 조건을 만족하지 못한다.

-> 그러므로 모든 xyz에 대해 조건을 충족하지 않는 어떤 s가 존재한다.
-> 귀류법에 의하여 B는 R.L이 아니다.