Formal Language는 특정 Alphabet 위의 String을 원소로 가지는 집합이다. 자연어에서는 문장의 의미가 중요하지만, Formal Language에서는 문자열이 정해진 규칙을 만족하여 집합에 속하는지가 핵심이다.

와

Alphabet 로 만들 수 있는 모든 유한 String의 집합을 라고 한다.

이므로 에는 항상 Empty String이 포함된다.

Empty String을 제외한 모든 String의 집합은 이다.

이면 는 다음과 같이 시작한다.

Language

Alphabet 위의 Language 은 의 부분집합이다.

예를 들어 1로 끝나는 Binary String의 Language는

로 나타낼 수 있다.

Language는 유한할 수도 있고 무한할 수도 있다. 은 유한 Language이고, 은 무한 Language이다.

집합 연산

Language는 Set이므로 일반적인 Set Operation을 적용할 수 있다.

Complement를 정의할 때에는 기준 Universe가 필요하다. Alphabet 가 고정되어 있다면

이다.

Language Concatenation

두 Language의 Concatenation은 각 Language에서 하나씩 String을 골라 이어 붙인 결과의 집합이다.

예를 들어

이면

이다. Language Concatenation도 일반적으로 교환법칙을 만족하지 않는다.

Language Power

로 정의한다. 이면

이다.

Kleene Star와 Positive Closure

Language를 0번 이상 반복하여 Concatenate한 모든 결과를 Kleene Star라고 한다.

0번 반복한 결과 때문에 가 항상 성립한다.

한 번 이상 반복한 결과는 Positive Closure이다.

예를 들어 이면

이다.

Reversal

String 의 Reversal은

이다. Language의 Reversal은 각 String을 뒤집은 집합이다.

Empty Language와 Empty String Language

다음 두 Language는 결과가 크게 다르다.

첫 식에서는 선택할 String 자체가 없고, 두 번째 식에서는 을 골라 이어 붙일 수 있기 때문이다.

정리

  • Formal Language는 의 부분집합이다.
  • 는 Empty String을 포함하고 는 포함하지 않는다.
  • Language는 Set Operation과 Concatenation을 가진다.
  • Kleene Star는 0번 이상의 반복이므로 항상 Empty String을 포함한다.

연습 문제

1번

, 일 때 , 을 구한다.

2번

일 때 , , 를 구하고 이 에 속하는지 판단한다.

풀이

1번

두 결과가 다르므로 Language Concatenation이 교환법칙을 만족하지 않는 예이기도 하다.

2번

로 분해할 수 있으므로 이다.