형식 언어

수학, 컴퓨터 과학, 언어학에서 형식 언어(形式言語, formal language)란, 특정한 법칙들에 따라 적절하게 구성된 문자열들의 집합을 말한다. 이는 수학기초론, 언어학, 정보이론의 핵심적 개념이며, 계산가능성 이론과 밀접하게 관련되어 있다.

정의

각 형식 언어에는 그 언어에서 사용하는 문자(alphabet)의 집합이 있으며, 그 집합은 무한할 수도 있다. 그 형식 언어에서 문자열(word)은 문자들로 이루어진 유한한 길이의 열(列)로 정의된다. 문자 집합을 $\Sigma$ 라고 정의했을 때, 그 문자들로 이루어진 모든 문자열의 집합은 $\Sigma ^{*}$ 가 된다.(별표는 클레이니 스타 연산자)

이 때, $\Sigma$ 위에 존재하는 형식 언어 $L$ 은 $\Sigma ^{*}$ 의 부분집합으로 정의된다.

형식 언어의 기술 방식

형식 언어는 특정한 문자열의 집합이기 때문에, 다음과 같은 방식을 이용해 형식 언어를 만들 수도 있다.

특정한 형식 문법의 법칙에 따라 생성되는 문자열의 집합
특정한 정규 표현식이 만들어내는 문자열의 집합
특정한 오토마톤이 받아들이는 문자열. 오토마톤에는 튜링 기계, 유한 상태 기계 등이 있다.
판정 문제의 대상이 되는 '예/아니오' 질문 중 그 대답이 '예'인 것들의 집합.
추론의 결과.

형식 언어의 연산

기존의 형식 언어를 결합하여 새로운 언어를 만들어 낼 수 있다. 두 형식 언어 L₁ 과 L₂가 있다고 하면, 다음과 같은 연산을 할 수 있다.

L₁ 과 L₂의 연쇄는 L₁의 문자열 v 와 L₂의 문자열 w를 연쇄시켜 만든 단어들의 집합이다. 표기: $L_{1}\cdot L_{2}$ 또는 $L_{1}L_{2}$ .
L₁ 과 L₂의 교집합은 L₁와 L₂ 에 동시에 속해 있는 문자열들의 집합이다. 표기 : $L_{1}\cap L_{2}\,$ .
L₁ 과 L₂의 합집합은 L₁에 속하거나 L₂ 에 속하는 문자열들의 집합이다. 표기 : $L_{1}\cup L_{2}\,$ 또는 $L_{1}+L_{2}$ .
L₁의 여집합은 L₁ 에 속하지 않는 문자열들의 집합이다.
우상(右商: 오른쪽 몫)은 L₂의 문자열 w에 대하여 vw가 L₁ 에 속하도록 하는 문자열 v의 집합이다. 표기 : $L_{1}/L_{2}$ .