형식 언어 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Syntax tree.svg|thumb]]
[[수학]], [[컴퓨터 과학]], [[언어학]]에서 '''형식 언어'''(形式言語, formal language)란, 특정한 법칙들에 따라 적절하게 구성된 문자열들의 집합을 말한다. 이는 [[수학기초론]], [[언어학]], [[정보이론]]의 핵심적 개념이며, [[계산가능성 이론]]과 밀접하게 관련되어 있다.

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

이 때, <math>\Sigma</math> 위에 존재하는 '''형식 언어''' <math>L</math>은 <math>\Sigma^*</math>의 [[부분집합]]으로 정의된다.

== 형식 언어의 기술 방식 ==
형식 언어는 특정한 문자열의 집합이기 때문에, 다음과 같은 방식을 이용해 형식 언어를 만들 수도 있다.
* 특정한 [[형식 문법]]의 법칙에 따라 생성되는 문자열의 집합
* 특정한 [[정규 표현식]]이 만들어내는 문자열의 집합
* 특정한 [[오토마톤]]이 받아들이는 문자열. 오토마톤에는 [[튜링 기계]], [[유한 상태 기계]] 등이 있다.
* [[판정 문제]]의 대상이 되는 '예/아니오' 질문 중 그 대답이 '예'인 것들의 집합.
* [[추론]]의 결과.

== 형식 언어의 연산 ==
기존의 형식 언어를 결합하여 새로운 언어를 만들어 낼 수 있다. 두 형식 언어 ''L''<sub>1</sub> 과 ''L''<sub>2</sub>가 있다고 하면, 다음과 같은 연산을 할 수 있다.

* ''L''<sub>1</sub> 과 ''L''<sub>2</sub>의 [[연쇄]]는 ''L''<sub>1</sub>의 문자열 ''v'' 와 ''L''<sub>2</sub>의 문자열 ''w''를 연쇄시켜 만든 단어들의 집합이다. 표기: <math>L_1\cdot L_2</math> 또는 <math>L_1 L_2</math>.
* ''L''<sub>1</sub> 과 ''L''<sub>2</sub>의 [[교집합]]은 ''L''<sub>1</sub>와 ''L''<sub>2</sub> 에 동시에 속해 있는 문자열들의 집합이다. 표기 : <math>L_1 \cap L_2\,</math>.
* ''L''<sub>1</sub> 과 ''L''<sub>2</sub>의 [[합집합]]은 ''L''<sub>1</sub>에 속하거나 ''L''<sub>2</sub> 에 속하는 문자열들의 집합이다. 표기 : <math>L_1 \cup L_2\,</math> 또는 <math>L_1 + L_2</math>.
* ''L''<sub>1</sub>의 [[여집합]]은 ''L''<sub>1</sub> 에 속하지 않는 문자열들의 집합이다.
* 우상(右商: 오른쪽 몫)은 ''L''<sub>2</sub>의 문자열 ''w''에 대하여 ''vw''가 ''L''<sub>1</sub> 에 속하도록 하는 문자열 ''v''의 집합이다. 표기 : <math>L_1 / L_2</math>.
== 같이 보기 ==
* [[문자열]]

== 외부 링크 ==
* {{위키공용분류-줄}}

{{형식언어 및 형식문법}}
{{전거 통제}}

[[분류:형식 언어| ]]
[[분류:이론 컴퓨터 과학]]