형식 언어 : Formal Language

컴파일러에 관해 공부하기 위해서는 우선, 컴퓨터 분야에서의 언어를 알아야한다. 이번에 공부할 형식언어의 정의는 다음과 같다.

형식 언어란, 특정한 법칙들에 따라 적절하게 구성된 문자열들의 집합을 말한다. 

언어에 관한 이론을 체계적으로 전개하기 위해서는 잘 정의된 언어를 필요로한다. 이와 같이 잘 정의된 언어를 형식언어(formal language)라고 부르며 보통 문장의 집합으로 정의된다.

 

형식언어에 대해 알기 전에 언어의 기본 단위 및 용어부터 정의해볼 필요가 있다.

• 알파벳(Alphabet) : 알파벳이란 문장을 이루는 기본적인 심벌로 심벌들의 유한집합을 얘기한다.

기본적인 내용이지만 예제를 통해서 살펴보자. 다음과 같이 집합 T1, T2, T3가 존재한다고 할때, 세 집합 모두 알파벳이라 칭할 수 있다. 반면에 T4는 유한집합이 아닌 무한집합이기 때문에 알파벳이 될 수 없다.

• 스트링(String) : 알파벳 T에 대하여 스트링이란, 알파벳 T에 속한 심벌 혹은 하나이상의 심벌들을 나열한 것을 말한다.
• 길이(Length) : 길이는 스트링을 이루는 심벌의 개수이며, 어떤 스트링 w의 길이는 |w|로 표기한다.

아래 그림은 스트링(String)과 길이(Length)에 대한 예시이다. 알파벳 T에 대한 스트링은 다음과 같다. 또한, 스트링의 길이는 ab = 2, abb = 3 이 된다.

• 접속(Concatenation) : 스트링의 접속은 스트링을 연속으로 연결한 것을 말한다.
• empty : empty 스트링은 스트링의 길이가 0인 스트링을 말하며 e(epsilon)으로 표기한다.
• T^*(Tstar) : 티스타는 empty 스트링을 포함하여 알파벳 T로부터 만들 수 있는 모든 스트링의 집합을 말한다.
• T^+(Tdagger) : 티대거는 티스타에서 empty 스트링을 제외한 스트링의 집합이다.