요약
- 정규 언어(Regular Language)는 유한 오토마타(FA)로 인식할 수 있는 언어의 집합이다
- 유한 오토마타는 "현재 상태"만 기억할 수 있기 때문에, 유한한 상태로 표현 가능한 패턴만 정규 언어가 된다
본문
유한 오토마타의 핵심 제약
유한 오토마타는 현재 상태만 기억할 수 있다. 이전에 무엇이 나왔는지, 몇 번 나왔는지를 기억하려면 그만큼의 상태가 필요하다.
정규 언어가 아닌 예: aⁿbⁿ
{aⁿbⁿ | n ≥ 0} (예: ab, aabb, aaabbb)는 정규 언어가 아니다.
- a가 3번 나온 것과 4번 나온 것을 구분하려면 상태 2개 필요
- a가 100번까지 구분하려면 상태 100개 필요
- n에 제한이 없으므로 무한한 상태가 필요 → 유한 오토마타로 불가능
정규 언어인 예: ab
a*b* (a가 0번 이상, b가 0번 이상)는 정규 언어다.
- a가 몇 개 나왔는지 기억할 필요 없음
- "지금 a를 읽는 단계인지, b를 읽는 단계인지"만 알면 됨
- 상태 2-3개로 충분
핵심 차이
| 언어 | 기억해야 하는 것 | 정규 언어 여부 |
|---|---|---|
| aⁿbⁿ | n의 값 (개수) | ❌ |
| ab | 현재 단계 (a인지 b인지) | ✅ |
참고
- 향후 추가: 정규 표현식의 실제 사용처 (입력 검증, 렉서, 텍스트 처리)
- 한계 사례: 중첩 구조(HTML, JSON, 괄호 매칭)는 정규 언어로 불가능
- Process는 프로그램의 인스턴스(실행중)이다. - 프로세스 상태(실행, 준비, 대기) 모델은 유한 상태 기계로 표현 가능. 입력에 따라 상태가 전이되는 구조가 유한 오토마타와 동일