---
title: "정규 언어: 유한 상태로 판정할 수 있는 문자열의 범위"
author: "Lee"
published_at: "2026-10-15T19:02:02.683Z"
updated_at: "2026-09-30T10:05:47.744Z"
tags: ["컴퓨터공학","계산이론"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%A0%95%EA%B7%9C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%95%9C-%EC%83%81%ED%83%9C%EB%A1%9C-%ED%8C%90%EC%A0%95%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8A%94-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%98-%EB%B2%94%EC%9C%84"
ai_assisted: false
---

# 정규 언어: 유한 상태로 판정할 수 있는 문자열의 범위

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%A0%95%EA%B7%9C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%95%9C-%EC%83%81%ED%83%9C%EB%A1%9C-%ED%8C%90%EC%A0%95%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8A%94-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%98-%EB%B2%94%EC%9C%84)

정규 언어는 유한 오토마타로 인식할 수 있는 문자열 집합이다. 여기서 언어는 자연어 전체가 아니라 어떤 규칙을 만족하는 문자열들의 모음을 뜻한다. 형식 언어 이론의 정규 표현식과 유한 오토마타는 같은 표현 능력을 가진다.

![접미사처럼 유한 기억으로 판정 가능한 규칙과 무제한 수량 비교가 필요한 규칙](/api/v1/media/070a6717-ef18-4498-8ceb-8a960b6f488c)

*정규 언어는 유한 상태로 인식 가능한 문자열 집합이며 표현 가능한 규칙에 한계가 있다.*

### 반복 규칙을 상태로 요약할 수 있는가

알파벳 {0,1}에서 1의 개수가 짝수인 문자열은 정규 언어다. 1의 정확한 개수를 끝없이 기억할 필요 없이 짝수·홀수 두 상태를 구별하면 된다. 고정 길이 접미사, 특정 패턴의 포함, 제한된 형식도 유한 상태로 표현할 수 있다.

정규 표현식의 기본 연산은 합집합, 이어 붙이기, 0회 이상 반복이다. (0|1)*은 모든 이진 문자열을 나타내고, (0|1)*01은 01로 끝나는 문자열을 나타낸다. ε는 길이 0인 문자열이며, 문자열이 하나도 없는 빈 언어와 다르다.

```text
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 실행과 다를 수 있다.

정규 언어는 컴파일러의 어휘 분석과 형식 검증의 중요한 기반이다. 유한 기억으로 충분한 규칙인지, 중첩이나 무제한 수량 비교가 필요한지 판단하면 정규식으로 해결할 문제의 경계를 알 수 있다.

고정된 최대 중첩 깊이의 괄호는 유한 상태로 표현할 수 있다. 괄호가 정규가 아니라는 설명에는 깊이를 제한하지 않는다는 조건이 포함되어야 한다.

### 참고 자료

- [MIT OpenCourseWare · Automata, Computability, and Complexity](https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/)