정규 언어

정규 언어(), 합리적 언어()는 이론 전산학, 형식 언어 이론에서 정규 표현식을 이용하여 표현할 수 있는 형식 언어이다.

정규 언어는 유한 상태 기계가 인지하는 언어로 정의할 수도 있다. 정규 표현식과 유한 상태 기계의 등가성은 클레이니의 정리로 알려져 있다. 촘스키 위계에서 정규 언어는 3형 문법(정규 문법)에 의해 생성되는 언어로 정의된다.

정규 언어는 입력 구문 분석(파싱)과 프로그래밍 언어 설계에 매우 유용하다.

 정의 

알파벳 Σ 위의 정규 언어의 집합은 다음과 같이 재귀적으로 정의할 수 있다.
 공집합 Ø은 정규 언어이다.
 각 글자 a ∈ Σ에 대해 한원소집합 {a}는 정규 언어이다.
 A가 정규 언어이면, 클레이니 스타를 붙인 A*도 정규 언어이다. (따라서 빈 문자열로만 이루어진 {ε}도 정규 언어이다.)
 A와 B가 정규 언어이면, 합집합 A ∪ B와 문자열 연결 AB도 정규 언어이다.
 그 밖의 언어는 정규 언어가 아니다.

 예시 
유한한 언어는 모두 정규 언어이다. 특히 {ε} = Ø*도 정규 언어이다. 알파벳 {a, b} 위의 정규 언어의 예로는 a를 짝수 개 포함하는 모든 문자열의 집합이나, a 여러 개 뒤에 b 여러 개가 오는 꼴인 모든 문자열의 집합 따위가 있다.

정규 언어가 아닌 언어의 예로 { anbn | n ≥ 0 }이 있다.Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2). 직관적으로 설명하면, 유한 상태 기계의 기억력은 유한하기 때문에 a가 몇 번 나왔는지 정확히 기억할 수 없으므로, 유한 상태 기계는 이 언어를 인지할 수 없기 때문이다.

 동등한 형식화 
형식언어 L이 정규 언어라는 것은 다음과 동치이다.
 L은 정규 표현식으로 나타낼 수 있다. (위의 정의)
 L은 비결정적 유한 상태 기계가 인지하는 언어이다.
 L은 결정적 유한 상태 기계가 인지하는 언어이다.
 L은 정규 문법이 생성하는 언어이다.
 L은 교대 유한 상태 기계(alternating finite automaton)가 인지하는 언어이다.
 L은 양쪽 유한 상태 기계(two-way finite automaton)가 인지하는 언어이다.
 L은 접두사 문법(prefix grammar)이 생성하는 언어이다.
 L은 읽기 전용 튜링 기계가 인지하는 언어이다.
 L은 일변수(monadic) 2차 논리에서 정의할 수 있는 언어이다. (뷔히-엘고트-트라크텐브로트 정리)M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002.

 닫힘 성질 
정규 언어의 집합은 여러 연산에 대해 닫혀 있다. K와 L이 정규 언어라면, 다음도 정규 언어이다.
 불 연산: 합집합 K ∪ L, 교집합 K ∩ L, 여집합 , 차집합 K - L.
 정규식 연산: K ∪ L, 문자열 연결 KL, 클레이니 스타 L*.
 h가 문자열 준동형사상일 때, h(L)과 h-1(L).
 임의의 언어 B에 대해, (오른쪽) 몫 B/L.
 거울상 LR.

 결정 가능성 
결정적 유한 상태 기계 A와 B가 주어졌을 때, 두 기계가 같은 언어를 인지하는지 결정할 수 있다.Hopcroft, Ullman (1979), Theorem 3.8, p.64; Theorem 3.10, p.67도 참조. 따라서 위의 닫힘 성질을 이용하면 두 기계가 인지하는 정규 언어 LA와 LB에 대해 다음 문제를 결정할 수 있다.
 포함: LA ⊆ LB인가?LA ∩ LB = LA인지 확인하면 된다.
 서로소: LA ∩ LB = Ø인가?
 공집합: LA = Ø인가?
 전체집합: LA = Σ*인가?
 소속: 주어진 a ∈ Σ*에 대해, a ∈ LA인가?

 촘스키 위계에서의 위치 
섬네일|촘스키 위계에서 정규 언어의 위치
모든 정규 언어는 문맥 자유 언어이다. 그러나 반대는 성립하지 않는다. { anbn | n ≥ 0 }는 문맥 자유 언어이지만 정규 언어가 아닌 예이다.

주어진 언어가 정규 언어인지 알아보려면 흔히 마이힐-네로드 정리나 펌핑 보조정리를 사용한다. 그 밖에 정규 언어의 닫힘 성질이나 콜모고로프 복잡도를 사용하는 방법도 있다.

 내용주 

 참조주 

 참고 문헌 




  Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
 Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics: Symbolic Combinatorics.  Online book, 2002.



 같이 보기 
 정규 표현식

 외부 링크 

 정규 언어 - 컴퓨터인터넷IT용어대사전

분류:형식 언어
분류:유한 상태 기계