정규 언어: 유한 상태로 판정할 수 있는 문자열의 범위
정규 언어는 유한 오토마타로 인식할 수 있는 문자열 집합이다. 여기서 언어는 자연어 전체가 아니라 어떤 규칙을 만족하는 문자열들의 모음을 뜻한다. 형식 언어 이론의 정규 표현식과 유한 오토마타는 같은 표현 능력을 가진다.
정규 언어는 유한 상태로 인식 가능한 문자열 집합이며 표현 가능한 규칙에 한계가 있다.
반복 규칙을 상태로 요약할 수 있는가
알파벳 {0,1}에서 1의 개수가 짝수인 문자열은 정규 언어다. 1의 정확한 개수를 끝없이 기억할 필요 없이 짝수·홀수 두 상태를 구별하면 된다. 고정 길이 접미사, 특정 패턴의 포함, 제한된 형식도 유한 상태로 표현할 수 있다.
정규 표현식의 기본 연산은 합집합, 이어 붙이기, 0회 이상 반복이다. (0|1)*은 모든 이진 문자열을 나타내고, (0|1)*01은 01로 끝나는 문자열을 나타낸다. ε는 길이 0인 문자열이며, 문자열이 하나도 없는 빈 언어와 다르다.
Alphabet: {0, 1}
Language: strings ending in 01
Examples accepted: 01, 001, 1101
Examples rejected: empty string, 0, 10, 011
Regular expression: (0|1)*01
A finite automaton only needs to remember the relevant suffix.
끝의 두 문자를 판단하려고 전체 문자열을 저장할 필요는 없다. 지금까지 읽은 접미사가 목표 패턴과 어디까지 맞는지만 몇 개 상태로 유지하면 된다.
모든 반복 구조가 정규인 것은 아니다
L={aⁿbⁿ | n≥0}는 a와 b의 개수가 정확히 같은지 무한 범위에서 비교해야 한다. 유한 상태만으로 앞의 a 개수를 제한 없이 기억할 수 없어 정규 언어가 아니다. 최대 개수를 고정하면 유한한 경우를 상태로 만들 수 있지만 그 제한을 제거한 문제와는 다르다.
펌핑 보조정리는 충분히 긴 정규 언어 문자열에서 반복 가능한 부분이 존재함을 말한다. aᵖbᵖ에서 앞 p문자 안의 비어 있지 않은 a 구간을 반복하면 a 수만 바뀌어 언어 밖으로 나간다. 이를 이용해 정규라는 가정에 모순을 만들 수 있다. 단순히 반복 부분이 안 보인다는 감상으로 증명하는 것은 아니다.
정규 언어는 합집합, 교집합, 여집합 등 여러 연산에 닫혀 있다. 예를 들어 두 조건의 DFA를 상태 쌍으로 묶으면 두 조건을 함께 판정할 수 있다. 다만 조합 과정에서 상태 수가 커질 수 있다.
실제 프로그래밍 언어의 정규식 엔진에는 역참조처럼 형식 이론의 정규 표현식보다 강한 기능이 포함될 수 있다. 어떤 엔진의 패턴이 모든 정규 언어 이론 성질을 그대로 갖는다고 가정해서는 안 된다. 백트래킹 구현의 실행 비용도 DFA 실행과 다를 수 있다.
정규 언어는 컴파일러의 어휘 분석과 형식 검증의 중요한 기반이다. 유한 기억으로 충분한 규칙인지, 중첩이나 무제한 수량 비교가 필요한지 판단하면 정규식으로 해결할 문제의 경계를 알 수 있다.
고정된 최대 중첩 깊이의 괄호는 유한 상태로 표현할 수 있다. 괄호가 정규가 아니라는 설명에는 깊이를 제한하지 않는다는 조건이 포함되어야 한다.