[Automata Theory] Language

언어(Language)라는 개념은 우리에게도 굉장히 친숙한 개념이다. 늘 사용하는 것이 언어이고 이 글도 언어의 한 종류인 한국어와 영어로 쓰여진 무언가 이다. 그렇다면 언어의 정의는 무엇일까?

 

우선, 언어를 정의하기 위해서는 '알파벳'과 '스트링'이라는 것이 필요하기에 이들을 먼저 알아보자.

 

1. 알파벳 $\Sigma$는 문자들의 Finite Set이다.

    예를 들어, 영어의 경우 $\Sigma=\{a, b,\cdots,z\}$이고, 이진수의 경우 $\Sigma=\{0,1\}$이다.

 

2. 스트링은 알파벳 $\Sigma$에 속해있는 문자들의 유한한 나열이다.

    예를 들어, "abcd"는 $\Sigma=\{a, b,\cdots,z\}$상의 스트링이다.

 

3. $\Sigma$상의 모든 스트링의 집합은 $\Sigma^*$이라고 하고, 이는 비어있는(길이가 0인) 스트링 $\epsilon$을 포함한다. 

    예를 들어, $\{0\}^*=\{\epsilon, 0, 00, 000, \cdots\}$이다.

 

기타 스트링에서의 prefix, suffix, concatenation 등은 일반적으로 우리가 알고 있는 사실과 같으므로 정의는 생략한다. 이제 언어를 정의해보자.

 

정의: 알파벳 $\Sigma$로 이루어진 언어 $L$은 $\Sigma^*$의 부분집합이다.

 

이제 언어와 관련된 몇 가지 개념과 용어들을 소개하겠다.

 

1. 두 언어 $L_1, L_2$의 concatenation: $L_1\cdot L_2=L_1L_2=\{xy:x\in L_1, y\in L_2\}$

 

2. 언어 $L$의 Kleene Star(Kleene Closure): $L^*=\displaystyle\bigcup_{i\geq 0}V^i$

 

 

 

* 이 글은 서울대학교 박근수 교수님의 '오토마타이론' 강의자료에 기반을 두고 있고, 교수님의 허락을 받고 포스팅을 진행함을 밝힌다.