오토마타 및 형식 언어

알파벳은 기호들의 유한하고 비어 있지 않은 집합이다. 알파벳의 각 원소를 기호 또는 문자라고 부른다. 예를 들어, 이진수 체계에서 사용하는 알파벳은 Σ = {0, 1}이며, 영어 소문자로 구성된 알파벳은 Σ = {a, b, c, ..., z}이다.

알파벳 Σ 위의 문자열은 Σ의 기호들을 유한하게 나열한 것이다. 문자열의 길이는 문자열을 구성하는 기호의 개수이다. 길이가 0인 특별한 문자열을 공 문자열이라고 하며, 보통 ε(엡실론) 또는 λ(람다) 기호로 표시한다. 예를 들어, 알파벳 Σ = {0, 1} 위에서 '001', '11010', 'ε'는 모두 문자열이다.

알파벳 Σ에 대해, Σ*는 Σ 위의 모든 가능한 유한 문자열(공 문자열 포함)의 집합을 나타낸다. 이 집합은 클레이니 스타 연산으로 생성된다. 반면, Σ+는 공 문자열을 제외한 모든 문자열의 집합, 즉 Σ* - {ε}을 의미한다. 형식 언어 이론에서 언어는 기본적으로 Σ*의 부분 집합으로 정의된다.

형식 언어는 알파벳 Σ 위에서 정의된 문자열의 집합이다. 여기서 알파벳 Σ는 기호들의 유한 집합을 의미하며, 이 알파벳의 기호들을 유한 개 연결하여 만든 것을 문자열(또는 단어)이라고 한다. 길이가 0인 특별한 문자열을 공 문자열이라고 하며, 보통 ε 또는 λ로 표기한다. 알파벳 Σ 위의 모든 가능한 문자열의 집합을 Σ*로 나타낸다. 따라서, 형식 언어 L은 Σ*의 부분 집합(L ⊆ Σ*)이다.

예를 들어, 알파벳 Σ = {0, 1}이 주어졌을 때, Σ*는 {ε, 0, 1, 00, 01, 10, 11, 000, ...}와 같은 모든 이진 문자열을 포함한다. 이때, "0으로 시작하는 모든 문자열의 집합"이나 "1의 개수가 짝수인 모든 문자열의 집합"은 각각 Σ*의 부분 집합이므로, 하나의 형식 언어를 정의한다. 언어는 유한할 수도 있고 무한할 수도 있다. 유한 언어의 예로는 {hello, world}가 있으며, 무한 언어의 예로는 모든 올바른 괄호 표현의 집합이 있다.

형식 언어 이론에서는 이러한 언어들을 어떻게 기술하고, 인식하고, 생성하는지에 초점을 맞춘다. 언어를 기술하는 방법에는 형식 문법을 사용하여 생성 규칙을 명시하는 방법, 오토마타를 사용하여 문자열을 인식하는 기계를 정의하는 방법, 또는 정규 표현식과 같은 수학적 표현을 사용하는 방법 등이 있다. 언어의 복잡도에 따라 이를 처리할 수 있는 오토마타나 문법의 종류가 달라지며, 이는 촘스키 위계로 체계화된다.

정규 언어는 촘스키 위계에서 가장 제한적인 형식 언어 계층인 Type-3 언어에 속한다. 이 언어들은 가장 단순한 형태의 규칙으로 생성되며, 유한 상태 오토마타(FSA)에 의해 인식될 수 있다. 정규 언어는 정규 표현식을 사용하여 간결하게 표현할 수 있다는 특징을 가진다.

정규 언어를 정의하는 방법은 크게 세 가지가 있다. 첫째, 정규 표현식을 사용하는 방법이다. 기본 연산인 합집합(∪), 접합(·), 클리니 스타(*)를 유한 번 적용하여 만들어진 표현식이 나타내는 언어가 정규 언어이다. 둘째, 유한 상태 오토마타에 의해 인식되는 언어로 정의하는 방법이다. 결정적 또는 비결정적 유한 오토마타가 모두 동일한 언어 집합을 인식한다. 셋째, 정규 문법에 의해 생성되는 언어로 정의할 수 있다. 정규 문법은 생성 규칙이 A → aB 또는 A → a 형태(우선형) 또는 A → Ba, A → a 형태(좌선형)로 제한된다.

정규 언어는 여러 중요한 폐쇄성 성질을 가진다. 합집합, 접합, 클리니 스타 연산에 대해 닫혀 있을 뿐만 아니라, 교집합, 여집합, 역 언어 연산에 대해서도 닫혀 있다[1]. 그러나 정규 언어의 무한 교집합은 정규 언어가 아닐 수 있다.

정규 언어의 한계를 보여주는 대표적인 정리는 펌핑 보조정리이다. 이 보조정리는 주어진 정규 언어 L에 대해, 충분히 긴 모든 문자열은 특정 조건을 만족하는 부분 문자열을 반복(펌핑)해도 여전히 L에 속한다는 내용이다. 이를 이용하여 특정 언어가 정규 언어가 아님을 증명할 수 있다. 예를 들어, 괄호의 쌍이 맞는 문자열의 집합이나, a^n b^n 형태의 언어는 펌핑 보조정리에 의해 정규 언어가 아님을 보일 수 있다.

정규 언어는 실용적으로 매우 널리 응용된다. 정규 표현식은 텍스트 편집기의 검색, 어휘 분석(토큰화), 간단한 패턴 매칭, 네트워크 프로토콜 설계 등 다양한 분야에서 사용된다.

문맥 자유 언어는 촘스키 위계에서 Type-2에 해당하는 언어의 부류이다. 이 언어는 문맥 자유 문법에 의해 생성되며, 푸시다운 오토마타에 의해 인식된다. 문맥 자유 언어는 정규 언어보다 더 넓은 표현력을 가지지만, 문맥 의존 언어보다는 제한적이다.

문맥 자유 문법의 생성 규칙은 A -> γ 형태를 가진다. 여기서 A는 하나의 비단말 기호이고, γ는 단말 기호와 비단말 기호로 이루어진 문자열이다. 이 규칙의 핵심은 좌변에 오직 하나의 비단말 기호만 존재한다는 점으로, 이로 인해 생성 과정이 주변 문맥(context)에 의존하지 않는다. 이러한 특성 덕분에 재귀 하강 파서와 같은 효율적인 파싱 알고리즘을 설계할 수 있다. 대표적인 예로는 대부분의 프로그래밍 언어의 구문 구조가 있다.

문맥 자유 언어의 중요한 성질과 한계는 펌핑 보조정리를 통해 설명된다. 이 보조정리는 모든 문맥 자유 언어가 일정 길이 이상의 문자열을 특정 방식으로 '펌핑'할 수 있음을 보장하며, 이를 이용해 특정 언어가 문맥 자유 언어가 아님을 증명할 수 있다. 예를 들어, {a^n b^n c^n | n >= 0}과 같은 언어는 문맥 자유 언어가 아니다[2]. 문맥 자유 언어는 합집합, 연결, 클레이니 스타 연산에 대해 닫혀 있지만, 교집합과 여집합 연산에 대해서는 일반적으로 닫혀 있지 않다.

이 언어 부류는 컴파일러의 구문 분석 단계에서 핵심적인 역할을 한다. LR 파서나 LL 파서는 문맥 자유 문법을 처리하도록 설계된 대표적인 파서이다.

문맥 의존 언어는 촘스키 위계에서 문맥 자유 언어보다 강력하지만 재귀 열거 언어보다는 제한된 형식 언어의 한 부류이다. 이 언어들은 문맥 의존 문법에 의해 생성되며, 선형 제한 오토마타에 의해 인식된다. 문맥 의존 언어의 핵심 특징은 생성 규칙의 좌변이 단일 비말단 기호가 아니라 주변 문맥을 포함할 수 있다는 점이다.

생성 규칙은 일반적으로 αAβ → αγβ의 형태를 가진다. 여기서 A는 비말단 기호이고, α와 β는 (공집합일 수 있는) 기호 문자열이며, γ는 공집합이 아닌 문자열이다[3]. 이는 치환 규칙의 적용이 특정 문맥(α와 β)에 의존한다는 것을 보여준다. 중요한 점은 규칙의 우변이 좌변보다 짧아서는 안 된다는 것이다(즉, |αAβ| ≤ |αγβ|). 이 비축약적 성질은 언어가 선형 제한 오토마타에 의해 결정 가능하다는 것을 보장한다.

문맥 의존 언어의 대표적인 예는 a^n b^n c^n (n ≥ 1)과 같은 언어이다. 이 언어는 세 종류의 기호 개수가 동일한 문자열의 집합으로, 문맥 자유 언어로는 표현할 수 없다. 문맥 의존 언어는 결정 가능 언어이며, 폐쇄성 성질에 대해 합집합, 교집합, 여집합, 연결 연산 등 여러 연산에 대해 닫혀 있다. 그러나 문맥 자유 언어와 달리 보편적 문맥 의존 언어는 존재하지 않는다는 것이 알려져 있다.

재귀 열거 언어는 촘스키 위계에서 가장 넓은 범주의 형식 언어이다. 이 언어들은 튜링 기계에 의해 인식(열거)될 수 있는 모든 언어의 집합으로 정의된다. 즉, 어떤 언어 L이 재귀 열거 언어일 필요충분조건은 L을 인식하는 튜링 기계가 존재하는 것이다. 여기서 '인식'은 입력 문자열이 언어에 속하면 기계가 정지하여 받아들이고, 속하지 않으면 정지하지 않거나 거부하는 것을 의미한다[4].

이 언어 계층은 문맥 의존 언어를 포함하며, 형식 문법으로는 모든 생성 규칙의 형태에 제약이 없는 무제약 문법(Type-0 문법)에 의해 생성된다. 재귀 열거 언어의 주요 특징은 결정 가능성이 보장되지 않는다는 점이다. 언어에 속하는 문자열은 유한 시간 내에 확인할 수 있지만, 언어에 속하지 않는 문자열에 대해서는 튜링 기계가 무한 루프에 빠져 영원히 답을 내지 않을 수 있다. 이러한 언어를 '재귀적으로 열거 가능'하다고 부른다.

재귀 열거 언어이면서 동시에 그 여집합도 재귀 열거 언어인 경우, 그 언어는 재귀 언어라고 불린다. 재귀 언어는 항상 결정 가능하다. 대표적인 재귀 열거 언어이지만 재귀 언어가 아닌 예로는 정지 문제의 인스턴스를 인코딩한 언어가 있다. 이는 튜링 기계의 계산 능력과 계산 이론의 근본적 한계를 보여주는 중요한 개념이다.

유한 상태 오토마타는 형식 언어 이론에서 가장 기본적인 계산 모델 중 하나이다. 특히 촘스키 위계에서 정규 언어를 인식하는 기계에 해당한다. 이 모델은 유한한 개수의 상태, 입력 알파벳, 상태 전이 함수, 시작 상태, 그리고 하나 이상의 종결 상태로 구성된다. 입력 문자열은 왼쪽에서 오른쪽으로 한 번에 하나의 심볼씩 읽히며, 각 입력 심볼에 따라 현재 상태가 전이 함수에 의해 다음 상태로 변경된다. 모든 입력을 읽은 후 기계가 종결 상태에 머물러 있으면 해당 문자열을 '인식' 또는 '수용'한다고 말한다.

유한 상태 오토마타는 결정적 유한 오토마타와 비결정적 유한 오토마타로 크게 구분된다. 결정적 유한 오토마타는 주어진 현재 상태와 입력 심볼에 대해 다음 상태가 정확히 하나로 정의된다. 반면, 비결정적 유한 오토마타는 같은 조건에서 여러 개의 다음 상태로 전이할 수 있는 가능성을 허용하며, 빈 문자열 입력(입력 없이 상태를 바꾸는 ε-전이)도 포함할 수 있다. 흥미롭게도 이 두 모델은 동등한 표현력을 가지며, 모든 비결정적 유한 오토마타는 결정적 유한 오토마타로 변환될 수 있다[5].

유한 상태 오토마타의 주요 성질과 응용은 다음과 같다.

이 모델의 한계는 유한한 메모리(상태)만을 가지기 때문에, 괄호의 짝 맞추기와 같이 임의의 깊이를 기억해야 하는 언어는 인식할 수 없다. 이러한 언어는 더 강력한 계산 모델인 푸시다운 오토마타가 필요하다.

푸시다운 오토마타는 유한 상태 오토마타를 확장한 계산 모델로, 무한한 용량을 가진 스택 메모리를 추가로 사용한다. 이 스택은 후입선출 방식으로 데이터를 저장하며, 오토마타의 상태 전이와 입력 심볼 읽기는 현재 스택의 최상단 심볼에 의존할 수 있다. 따라서 PDA는 문맥 자유 언어를 인식하는 능력을 가지며, 정규 언어보다 더 넓은 범위의 언어를 처리할 수 있다.

PDA는 7-튜플 (Q, Σ, Γ, δ, q0, Z0, F)로 형식적으로 정의된다. 여기서 Q는 상태들의 유한 집합, Σ는 입력 알파벳, Γ는 스택 알파벳, δ는 전이 함수, q0는 초기 상태, Z0는 초기 스택 심볼, F는 최종 상태 집합이다. 전이 함수 δ는 현재 상태, 입력 심볼(또는 ε), 스택 최상단 심볼을 받아 다음 상태와 스택 최상단을 교체할 심볼 문자열을 출력한다.

PDA는 결정적 푸시다운 오토마타와 비결정적 푸시다운 오토마타로 구분된다. 결정적 PDA는 주어진 상황에서 가능한 전이가 최대 하나뿐이어야 하지만, 비결정적 PDA는 여러 전이가 가능하다. 중요한 사실은 결정적 PDA가 인식할 수 있는 언어의 범위가 비결정적 PDA가 인식하는 문맥 자유 언어 전체보다 좁다는 점이다. 즉, 모든 문맥 자유 언어가 결정적 PDA에 의해 인식되는 것은 아니다.

PDA의 주요 응용 분야는 프로그래밍 언어의 구문 분석이다. 대부분의 프로그래밍 언어의 문법은 문맥 자유 문법으로 표현되며, 이를 위한 파서는 본질적으로 PDA의 원리를 구현한다. 예를 들어, 괄호의 짝을 맞추거나 중위 표기법을 처리하는 작업은 스택 없이는 불가능하며, PDA가 이러한 문제를 해결하는 표준 모델이 된다.

선형 제한 오토마타(LBA)는 튜링 기계의 특수한 형태로, 테이프의 사용 가능한 공간이 입력 문자열의 길이에 선형적으로 비례하도록 제한된 계산 모델이다. 즉, 입력 문자열의 길이가 n일 때, 테이프 셀을 cn개(c는 상수) 이상 사용할 수 없다. 이 공간 제약은 문맥 의존 언어(Type-1)를 인식하는 능력과 밀접하게 연결되어 있다.

LBA의 구성은 튜링 기계와 유사하게 상태, 입력 알파벳, 테이프 알파벳, 전이 함수, 시작 상태, 종결 상태로 이루어져 있다. 핵심 차이는 테이프 헤드가 입력의 왼쪽과 오른쪽 끝을 표시하는 특수 기호 사이에서만 이동할 수 있다는 점이다. 이 경계 기호는 헤드가 지나갈 수 없으며, 테이프 공간이 선형적으로 제한되는 효과를 만들어낸다.

촘스키 위계에서 LBA는 문맥 의존 언어를 정확히 인식하는 기계로 알려져 있다. 이는 중요한 정리로, 모든 문맥 의존 문법에 의해 생성되는 언어는 어떤 LBA에 의해 인식되며, 그 역도 성립한다. 그러나 LBA에 대한 결정 문제는 여전히 흥미로운 미해결 문제를 남겼다. LBA가 주어진 언어를 인식하는지 여부를 판단하는 문제는 결정 가능한지 알려져 있지 않다. 이는 튜링 기계의 정지 문제가 결정 불가능한 것과는 대조적이다.

LBA는 계산 복잡도 이론에서 중요한 위치를 차지하며, 특히 PSPACE 복잡도 부류를 정의하는 데 기초가 된다. 다항식 공간을 사용하는 문제들은 LBA의 개념을 확장한 기계로 해결할 수 있다.

튜링 기계는 앨런 튜링이 1936년에 제안한 추상적인 계산 모델이다. 이 모델은 계산 가능성과 알고리즘의 개념을 형식화하기 위해 고안되었다. 튜링 기계는 무한히 긴 테이프, 테이프를 읽고 쓸 수 있는 헤드, 그리고 유한한 상태를 가진 제어 장치로 구성된다. 테이프는 셀들로 나뉘며, 각 셀에는 기호를 하나 저장할 수 있다. 튜링 기계는 현재 상태와 헤드가 읽은 기호에 따라 다음 상태, 쓸 기호, 그리고 헤드의 이동 방향(좌측 또는 우측)을 결정하는 규칙에 따라 동작한다.

튜링 기계는 촘스키 위계에서 가장 강력한 형식 언어인 재귀 열거 언어를 인식할 수 있으며, 계산 이론에서 '계산 가능한 함수'를 정의하는 표준 모델로 받아들여진다. 튜링 완전성을 가진 모든 계산 모델은 튜링 기계와 동등한 계산 능력을 지닌다. 이는 현대의 모든 범용 디지털 컴퓨터가 튜링 기계와 동등한 계산 능력을 가짐을 의미한다.

튜링 기계는 결정적 버전과 비결정적 버전으로 구분된다. 그러나 앨런 튜링이 증명한 바와 같이, 비결정적 튜링 기계는 결정적 튜링 기계에 의해 시뮬레이션될 수 있다[6]. 튜링 기계의 중요한 변형으로는 테이프가 여러 개인 다중 테이프 튜링 기계와 테이프의 사용에 제약을 가한 선형 제한 오토마타 등이 있다. 이들 변형은 계산 능력 면에서는 기본적인 단일 테이프 튜링 기계와 동등하지만, 특정 문제를 해결하는 효율성(예: 시간 복잡도)에는 차이를 보일 수 있다.

튜링 기계의 개념은 정지 문제와 같은 결정 불가능 문제를 증명하는 데 핵심적으로 사용된다. 정지 문제는 주어진 튜링 기계와 입력이 유한 시간 내에 정지할지 여부를 판단하는 일반적인 알고리즘이 존재하지 않음을 보여준다. 이 결과는 계산의 근본적인 한계를 규정하며, 계산 복잡도 이론과 수리 논리학의 기초를 이루는 중요한 정리이다.

생성 규칙은 형식 문법의 핵심 구성 요소로, 문법이 어떻게 문자열을 생성하는지를 정의하는 규칙들의 집합이다. 이 규칙들은 주로 'A → β'와 같은 형태를 가지며, 여기서 A는 비단말 기호이고 β는 단말 기호와 비단말 기호로 구성된 문자열이다. 이 규칙은 "A를 β로 치환할 수 있다"는 의미를 가진다. 생성 규칙의 집합은 촘스키 위계에 따라 문법의 능력을 결정하며, 이는 인식하는 언어의 복잡성과 직접적으로 연결된다.

생성 규칙의 적용은 유도 과정을 통해 이루어진다. 시작 기호에서 출발하여, 생성 규칙을 반복적으로 적용하여 최종적으로 단말 기호만으로 이루어진 문자열을 만들어내는 것이 목표이다. 예를 들어, 간단한 산술 표현식 문법에서는 E → E + E 또는 E → number와 같은 규칙을 가질 수 있다. 여기서 E는 표현식을 나타내는 비단말 기호이고, number는 단말 기호이다. 이 규칙들을 사용하면 E에서 시작해 E + E, number + E, number + number와 같은 유도를 통해 3 + 5와 같은 문자열을 생성할 수 있다.

생성 규칙의 형태는 문법의 유형을 구분하는 기준이 된다. 정규 문법의 규칙은 A → aB 또는 A → a와 같은 선형 형태를 가지는 반면, 문맥 자유 문법의 규칙은 좌변에 단일 비단말 기호만 허용된다(A → γ). 문맥 의존 문법에서는 규칙의 적용이 주변 문맥에 의존하며(예: αAβ → αγβ), 무제한 문법에서는 어떠한 형태의 규칙도 허용된다. 이러한 차이는 각 문법이 생성할 수 있는 언어의 범위와 그 언어를 인식하는 데 필요한 오토마타의 계산 능력을 규정한다.

파싱은 주어진 문자열이 특정 형식 문법에 의해 생성될 수 있는지 확인하고, 그 과정을 분석하는 절차이다. 구문 분석이라고도 불린다. 유도는 문법의 생성 규칙을 반복적으로 적용하여 시작 기호로부터 특정 문자열을 만들어내거나, 반대로 주어진 문자열로부터 시작 기호로 거슬러 올라가는 과정을 의미한다.

파싱은 크게 하향식 파싱과 상향식 파싱으로 나뉜다. 하향식 파싱은 시작 기호에서 시작하여 문자열을 만들어나가는 방식으로, 최좌단 유도와 밀접한 관련이 있다. 반면 상향식 파싱은 주어진 문자열의 단말 기호들로부터 시작하여 시작 기호로 축약해 나가는 방식으로, 최우단 유도의 역과정에 해당한다. 각 방식은 서로 다른 종류의 파서를 설계하는 데 사용된다.

유도 과정은 파스 트리라는 트리 구조로 시각화될 수 있다. 동일한 문자열에 대해 서로 다른 유도 순서가 존재할 수 있으며, 이는 문법의 모호성과 연결된다. 문맥 자유 문법에서 파싱 알고리즘의 대표적인 예로는 CYK 알고리즘과 Earley 파서가 있다. 이 알고리즘들은 주어진 문자열이 문법에 속하는지를 결정하고, 필요한 경우 파스 트리를 구성한다.

파싱과 유도 이론은 컴파일러의 구문 분석기 설계에 직접적으로 적용된다. 프로그래밍 언어의 소스 코드는 문자열이며, 이를 해당 언어의 문법에 맞는 파스 트리로 변환하는 것이 구문 분석기의 핵심 임무이다.

펌핑 보조정리는 형식 언어 이론에서 특정 언어가 특정 언어 계층에 속하지 않음을 증명하기 위해 널리 사용되는 강력한 도구이다. 이 보조정리는 주어진 언어가 정규 언어나 문맥 자유 언어가 될 수 없음을 보여주는 데 자주 활용된다. 그 핵심 아이디어는, 만약 언어가 해당 언어 계층에 속한다면 충분히 긴 문자열은 특정 부분을 반복해서 '펌핑'(pump)하더라도 여전히 그 언어에 속해야 한다는 것이다. 이 필수 조건을 위반하는 반례를 구성함으로써 언어가 해당 계층에 속할 수 없음을 증명한다.

가장 잘 알려진 것은 정규 언어에 대한 펌핑 보조정리이다. 이는 모든 정규 언어 L에 대해, L에 속하는 충분히 긴 문자열 w는 w = xyz 형태로 분해될 수 있으며, 다음 세 조건을 만족한다는 내용이다.

1. |y| > 0

2. |xy| ≤ p (p는 펌핑 길이 상수)

3. 모든 i ≥ 0에 대해, xyⁱz ∈ L

즉, 부분 문자열 y를 0번 이상 반복하여 생성된 새로운 문자열도 모두 언어 L에 속해야 한다. 예를 들어, 언어 L = {aⁿbⁿ | n ≥ 0}가 정규 언어가 아님을 보이기 위해, 이 조건을 만족하는 펌핑 길이 p를 가정하고 문자열 w = aᵖbᵖ를 고려한다. 어떤 방식으로 w를 xyz로 분해하더라도 y가 a만으로 구성되면, y를 반복했을 때 a와 b의 개수가 달라져 언어에서 벗어나게 되어 모순이 발생한다.

비슷한 원리가 문맥 자유 언어에 대한 펌핑 보조정리(흔히 욕기-우딜레미 정리라고도 함)에도 적용된다. 이 버전은 문자열을 uvxyz의 다섯 부분으로 나누며, v와 y를 동시에 펌핑한다. 이를 이용하면 언어 L = {aⁿbⁿcⁿ | n ≥ 0}가 문맥 자유 언어가 아님을 증명할 수 있다[7]. 펌핑 보조정리는 언어의 비정규성이나 비문맥자유성을 보이는 데 필수적인 도구지만, 그 역은 성립하지 않는다. 즉, 펌핑 조건을 만족한다고 해서 그 언어가 반드시 정규 언어 또는 문맥 자유 언어인 것은 아니다.

폐쇄성 성질은 특정 연산을 수행했을 때, 주어진 언어의 부류가 그 결과로 생성된 새로운 언어를 여전히 포함하는지를 나타낸다. 예를 들어, 어떤 언어 부류가 합집합, 교집합, 여집합, 연결, 클레이니 스타 등의 연산에 대해 닫혀 있다면, 그 부류에 속하는 언어들에 해당 연산을 적용해 얻은 새로운 언어도 동일한 부류에 속한다는 것을 의미한다.

주요 언어 부류별 폐쇄성은 다음과 같이 정리된다.

이 표에서 '닫힘'은 해당 연산에 대해 폐쇄적임을, '닫히지 않음'은 폐쇄적이지 않음을 의미한다. 예를 들어, 정규 언어는 모든 기본 연산에 대해 폐쇄적이지만, 문맥 자유 언어는 교집합과 여집합 연산에 대해서는 폐쇄적이지 않다. 이는 두 개의 문맥 자유 언어를 교집합하거나, 하나의 문맥 자유 언어의 여집합을 취했을 때 그 결과가 문맥 자유 언어가 아닐 수 있음을 보여준다.

폐쇄성 성질은 언어의 복잡성을 분석하고, 특정 문제가 어떤 언어 부류에 속하는지 판단하는 데 유용하게 활용된다. 또한, 오토마타 모델의 능력을 이해하는 데 중요한 이론적 토대를 제공한다. 예를 들어, 정규 언어가 합집합과 여집합에 대해 닫혀 있다는 사실은 유한 상태 오토마타로 구성된 두 개의 오토마타가 주어졌을 때, 그들의 합집합이나 여집합을 인식하는 새로운 유한 상태 오토마타를 구성할 수 있음을 의미한다.

결정 가능성은 주어진 문제에 대해 항상 정답을 '예' 또는 '아니오'로 내놓는 알고리즘이 존재함을 의미한다. 이러한 문제를 결정 문제라고 하며, 이를 해결하는 알고리즘 또는 기계를 결정기라고 한다. 예를 들어, 주어진 문자열이 특정 정규 언어에 속하는지 여부는 유한 상태 오토마타를 통해 항상 결정 가능하다.

반면, 결정 불가능성은 어떤 문제에 대해 그 문제의 모든 인스턴스에 대해 항상 정지하고 정확한 답을 내놓는 알고리즘이 존재하지 않음을 의미한다. 가장 유명한 예는 정지 문제이다. 정지 문제는 임의의 튜링 기계와 입력이 주어졌을 때, 그 기계가 해당 입력에 대해 유한 시간 내에 정지할지 아니면 무한히 실행될지를 판단하는 문제이다. 앨런 튜링은 이 문제가 결정 불가능함을 증명했다[8].

형식 언어 이론에서 언어의 종류에 따라 결정 가능한 문제의 범위가 달라진다. 아래 표는 주요 언어 계층별 몇 가지 대표적인 결정 가능/불가능 문제를 보여준다.

결정 불가능성의 발견은 계산 이론의 근본적인 한계를 보여주며, 모든 수학적 문제를 알고리즘적으로 해결할 수 없다는 점을 시사한다. 이는 컴퓨터 과학의 철학적 기초를 마련하는 중요한 개념이 되었다.

컴파일러 설계는 오토마타와 형식 언어 이론의 가장 중요한 응용 분야 중 하나이다. 컴파일러는 고수준 프로그래밍 언어로 작성된 소스 코드를 저수준의 기계어로 변환하는 프로그램으로, 그 과정은 여러 단계를 거친다. 이 중 초기 단계인 어휘 분석과 구문 분석은 각각 정규 언어와 문맥 자유 언어 이론에 직접적으로 기반을 두고 있다.

어휘 분석 단계에서는 소스 코드의 문자열을 토큰이라는 의미 있는 최소 단위로 분리한다. 이 과정은 주로 유한 상태 오토마타의 개념을 구현한 정규 표현식을 사용하여 기술된다. 예를 들어, 식별자, 정수 리터럴, 연산자, 예약어 등의 패턴은 정규 표현식으로 정의되며, 어휘 분석기(렉서)는 이 패턴들을 인식하여 토큰 스트림을 생성한다. 이는 정규 언어가 유한 오토마타에 의해 인식된다는 이론적 배경과 정확히 일치한다.

구문 분석 단계에서는 토큰 스트림이 프로그래밍 언어의 문법에 맞는 구조를 가지고 있는지 검증하고, 파스 트리나 추상 구문 트리와 같은 계층적 자료 구조를 생성한다. 프로그래밍 언어의 대부분의 구문 구조는 문맥 자유 문법으로 기술 가능하며, 따라서 구문 분석기는 문맥 자유 언어를 처리하는 푸시다운 오토마타의 원리를 활용한다. 대표적인 구문 분석 알고리즘으로는 LL 파서와 LR 파서가 있으며, 이들은 각각 하향식 구문 분석과 상향식 구문 분석 방식을 구현한 것이다.

이론과 실제의 이러한 긴밀한 연결 덕분에, 어휘 분석기 생성기나 파서 생성기와 같은 도구들을 안정적으로 개발하고 사용할 수 있다. 이 도구들은 형식적으로 정의된 문법 명세를 입력받아, 해당 언어를 인식하는 효율적인 분석기 코드를 자동으로 생성해낸다.

정규 표현식은 정규 언어를 표현하기 위한 강력한 표기법이다. 특정 패턴을 가진 문자열의 집합을 간결하게 기술하는 데 사용되며, 기본 연산자로 합집합, 연접, 클레이니 스타를 포함한다. 예를 들어, 정규 표현식 (a|b)*c는 'a'와 'b'가 0번 이상 반복된 후 'c'로 끝나는 모든 문자열의 집합을 나타낸다.

패턴 매칭은 주어진 문자열이 특정 패턴을 만족하는지 검사하거나, 패턴에 부합하는 부분 문자열을 찾는 과정이다. 정규 표현식은 이러한 패턴을 정의하는 사실상의 표준으로, 유한 상태 오토마타와 밀접한 관련이 있다. 모든 정규 표현식은 이를 인식하는 비결정적 유한 오토마타(NFA)로 변환될 수 있으며, 다시 결정적 유한 오토마타(DFA)로 변환하여 효율적인 패턴 매칭 알고리즘의 기초를 제공한다[10].

정규 표현식은 Perl, Python, grep, sed를 비롯한 대부분의 현대 프로그래밍 언어와 텍스트 처리 도구에 내장되어 있다. 그러나 표현력의 한계로 인해 문맥 자유 언어에 속하는 중첩된 구조(예: 괄호 짝 맞추기)는 표현하지 못한다는 점에 유의해야 한다. 이러한 복잡한 패턴 매칭은 푸시다운 오토마타와 문맥 자유 문법의 영역에 속한다.

프로토콜 검증은 통신 프로토콜이나 분산 시스템의 설계가 명세된 요구사항을 만족하는지, 교착 상태나 라이브락 등의 오류 상태에 빠지지 않는지를 수학적으로 분석하고 확인하는 과정이다. 형식 검증의 한 분야로, 오토마타 이론과 형식 언어가 그 기초를 제공한다. 시스템의 동작을 유한 상태 오토마타나 상태 전이 시스템 같은 형식 모델로 추상화한 후, 원하는 성질(예: 특정 상태 도달 불가, 두 프로세스가 동시에 임계 구역에 진입하지 않음)을 임시 논리 같은 형식 명세 언어로 표현한다. 검증 도구는 이 모델이 명세를 만족하는지 자동으로 검사한다.

가장 널리 사용되는 접근법은 모델 체킹이다. 시스템의 가능한 모든 상태 공간을 탐색하여 명세 위반이 있는지 확인하는 알고리즘적 방법이다. 프로토콜의 상태 수가 유한할 때 효과적이다. 예를 들어, 통신 프로토콜에서 "송신자가 데이터를 보낸 후, 수신자의 확인 응답을 받기 전에는 같은 데이터를 다시 보내지 않는다"는 성질을 검증할 수 있다. 복잡한 프로토콜의 경우 상태 공간 폭발 문제가 발생할 수 있어, 기호적 모델 체킹이나 축소 기법이 동원된다.

프로토콜 검증의 주요 응용 분야는 다음과 같다.

이 분야는 에드스거 데이크스트라, 아밀 푸르누알라 등의 선구적 연구를 바탕으로 발전했으며, SPIN, UPPAAL, NuSMV 같은 도구들이 실용적으로 널리 사용된다. 이를 통해 설계 단계에서 오류를 발견함으로써 시스템의 신뢰성을 크게 높일 수 있다.