형식 언어

수학, 컴퓨터 과학, 언어학에서 형식 언어(形式言語, 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}$.