정규 언어 (regular language ), 합리적 언어 (rational language )[ 1] [ 2] 이론 전산학 , 형식 언어 이론 에서 정규 표현식 을 이용하여 표현할 수 있는 형식 언어 이다.
정규 언어는 유한 상태 기계 가 인지하는 언어로 정의할 수도 있다. 정규 표현식과 유한 상태 기계의 등가성은 클레이니 의 정리[ 3] 촘스키 위계 에서 정규 언어는 3형 문법(정규 문법 )에 의해 생성되는 언어로 정의된다.
정규 언어는 입력 구문 분석 (파싱)과 프로그래밍 언어 설계에 매우 유용하다.
알파벳 Σ 위의 정규 언어의 집합은 다음과 같이 재귀적으로 정의할 수 있다.
공집합 Ø은 정규 언어이다.
각 글자 a ∈ Σ에 대해 한원소집합 {a }는 정규 언어이다.
A가 정규 언어이면, 클레이니 스타 를 붙인 A* 도 정규 언어이다. (따라서 빈 문자열로만 이루어진 {ε}도 정규 언어이다.)
A와 B가 정규 언어이면, 합집합 A ∪ B와 문자열 연결 AB도 정규 언어이다.
그 밖의 언어는 정규 언어가 아니다.
유한한 언어는 모두 정규 언어이다. 특히 {ε} = Ø* 도 정규 언어이다. 알파벳 {a , b } 위의 정규 언어의 예로는 a 를 짝수 개 포함하는 모든 문자열의 집합이나, a 여러 개 뒤에 b 여러 개가 오는 꼴인 모든 문자열의 집합 따위가 있다.
정규 언어가 아닌 언어의 예로 { an bn | n ≥ 0 }이 있다.[ 4] a 가 몇 번 나왔는지 정확히 기억할 수 없으므로, 유한 상태 기계는 이 언어를 인지할 수 없기 때문이다.
형식언어 L 이 정규 언어라는 것은 다음과 동치이다.
L 은 정규 표현식 으로 나타낼 수 있다. (위의 정의)L 은 비결정적 유한 상태 기계 가 인지하는 언어이다.[ a] [ b] L 은 결정적 유한 상태 기계 가 인지하는 언어이다.[ c] [ d] L 은 정규 문법 이 생성하는 언어이다.[ e] [ f] L 은 교대 유한 상태 기계 (alternating finite automaton)가 인지하는 언어이다.L 은 양쪽 유한 상태 기계 (two-way finite automaton)가 인지하는 언어이다.L 은 접두사 문법 (prefix grammar)이 생성하는 언어이다.L 은 읽기 전용 튜링 기계 가 인지하는 언어이다.L 은 일변수(monadic) 2차 논리 에서 정의할 수 있는 언어이다. (뷔히-엘고트-트라크텐브로트 정리)[ 5]
정규 언어의 집합은 여러 연산에 대해 닫혀 있다. K 와 L 이 정규 언어라면, 다음도 정규 언어이다.
불 연산: 합집합 K ∪ L , 교집합 K ∩ L , 여집합 L , 차집합 K - L .
정규식 연산: K ∪ L , 문자열 연결 KL , 클레이니 스타 L * .
h 가 문자열 준동형사상 일 때, h (L )과 h -1 (L ).임의의 언어 B 에 대해, (오른쪽) 몫 B /L .
거울상 L R .
결정적 유한 상태 기계 A와 B가 주어졌을 때, 두 기계가 같은 언어를 인지하는지 결정할 수 있다.[ 9] LA 와 LB 에 대해 다음 문제를 결정할 수 있다.
포함: L A L B [ g]
서로소: L A L B
공집합: L A
전체집합: L A * 인가?
소속: 주어진 a ∈ Σ* 에 대해, a ∈ L A
촘스키 위계에서 정규 언어의 위치 모든 정규 언어는 문맥 자유 언어 이다. 그러나 반대는 성립하지 않는다. { an bn | n ≥ 0 }는 문맥 자유 언어이지만 정규 언어가 아닌 예이다.
주어진 언어가 정규 언어인지 알아보려면 흔히 마이힐-네로드 정리 나 펌핑 보조정리 를 사용한다. 그 밖에 정규 언어의 닫힘 성질이나 콜모고로프 복잡도 를 사용하는 방법도 있다.[ 10]
↑ 1 ⇒ 2: 톰슨 구성
↑ 2 ⇒ 1: 클레이니 알고리즘 또는 아덴 보조정리
↑ 2 ⇒ 3: 멱집합 구성
↑ 3 ⇒ 2: 모든 결정적 유한 상태 기계는 비결정적 유한 상태 기계이므로.
↑ 2 ⇒ 4: Hopcroft, Ullman (1979), Theorem 9.2, p.219 참조
↑ 4 ⇒ 2: Hopcroft, Ullman (1979), Theorem 9.1, p.218 참조
↑ L A L B L A
↑ Ruslan Mitkov (2003). 《The Oxford Handbook of Computational Linguistics》 . Oxford University Press. 754쪽. ISBN 978-0-19-927634-9 ↑ Mark V. Lawson (2003). 《Finite Automata》 . CRC Press. 98–103쪽. ISBN 978-1-58488-255-8 ↑ Sheng Yu (1997). 〈Regular languages〉. Grzegorz Rozenberg and Arto Salomaa. 《Handbook of Formal Languages: Volume 1. Word, Language, Grammar》 . Springer. 41쪽. ISBN 978-3-540-60420-4 ↑ Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.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.
↑ Hopcroft, Ullman (1979), Theorem 3.8, p.64; Theorem 3.10, p.67도 참조.
↑ Hromkovič, Juraj (2004). 《Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography》 . Springer. 76–77쪽. ISBN 3-540-14015-8 OCLC 53007120 .
Berstel, Jean; Reutenauer, Christophe (2011). 《Noncommutative rational series with applications》. Encyclopedia of Mathematics and Its Applications 137 . Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0 Zbl 1250.68007 . Eilenberg, Samuel (1974). 《Automata, Languages, and Machines. Volume A》. Pure and Applied Mathematics 58 . New York: Academic Press. Zbl 0317.94045 . Salomaa, Arto (1981). 《Jewels of Formal Language Theory》. Pitman Publishing. ISBN 0-273-08522-0 Zbl 0487.68064 . Sipser, Michael (1997). 《Introduction to the Theory of Computation》 . PWS Publishing. ISBN 0-534-94728-X Zbl 1169.68300 . Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics : Symbolic Combinatorics. Online book, 2002.
John E. Hopcroft; Jeffrey D. Ullman (1979). 《Introduction to Automata Theory, Languages, and Computation》 . Addison-Wesley. ISBN 0-201-02988-X Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974). 《The Design and Analysis of Computer Algorithms》 . Addison-Wesley.
각 언어 및 문법은 바로 윗줄의
진부분집합 이다. 또한 각 기계와 문법은 바로 윗줄의 기계와 문법으로 동등하게 기술될 수 있다.
정규 표현식 문서를 참고하십시오.
