형식 언어

위키백과 ― 우리 모두의 백과사전.

형식 언어(形式言語, formal language)는 자연 과학, 법학, 언어학 등의 학문 분야의 여러 맥락에서 사용되는 용어로 일상 언어 또는 자연언어에 비해 매우 형식적이고 정확한 표현 양식을 가진 언어를 가리킨다.

형식 언어는 좁게는 수학, 논리학, 전산학에서 사용되는 개념으로 유한한 종류의 기호 또는 문자로 이루어진 유한한 길이의 단어 (문자열)들의 집합을 말한다. 이러한 대상을 다루는 과학 이론을 형식 언어 이론이라고 한다.

형식 언어는 논리학과 정보 이론의 연구 대상이기도 하며 이러한 연구는 계산가능성 이론과 밀접하게 관련되어 있다.

[편집] 형식 언어의 구성

형식 언어는 다음과 같이 다양한 방식으로 기술될 수 있다.

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

다양한 연산을 이미 알려진 언어들에 적용해 새로운 언어를 만들어 낼 수 있다. 두 형식언어 L₁ 과 L₂ 가 있다고 하면 다음과 같은 연산이 가능하다.

• L₁ 과 L₁ 의 연쇄는 L₁ 의 문자열 v 와 L₂ 의 문자열 w 를 연쇄시켜 만든 단어들의 집합이다. 표기: 또는 L₁L₂.
• L₁ 과 L₂ 의 교집합은 L₁와 L₂ 에 동시에 속해 있는 문자열들의 집합이다. 표기 : .
• L₁ 과 L₂ 의 합집합은 L₁에 속하거나 L₂ 에 속하는 문자열들의 집합이다. 표기 : ou L₁ + L₂.
• L₁ 의 여집합은 L₁ 에 속하지 않는 문자열들의 집합이다.
• 우상 (오른쪽 몫) L₁/L₂ 는 L₂의 문자열 w 에 대하여 vw가 L₁ 에 속하도록 하는 문자열 v 의 집합이다. 표기 : L₁ / L₂.

이 문서는 언어학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

오토마타 이론: 형식 언어 및 형식 문법
촘스키 위계	형식 문법	형식 언어	최소한의 자동장치
Type-0	(무제약)	순환 열거 언어	튜링 기계
	(무제약)	순환 언어	판정자
Type-1	문맥 의존 문법	문맥 의존 언어	선형유한 오토마타
Type-2	문맥 무관 문법	문맥 무관 언어	내리누름 오토마타
Type-3	정규 문법	정규 언어	유한 오토마타
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다.