Introduction

---

형식 언어란?

형식 언어는 문자열의 집합으로, 이를 생성하거나 구분하기 위한 **규칙(문법)**에 의해 정의됩니다. 계산 이론에서는 형식 언어가 언어의 구조를 수학적으로 분석하고 처리하는 데 사용됩니다.

---

계산 이론에서 형식 언어의 종류

1. 정규 언어
   • 문법: 정규 문법 (Type-3)
   • 오토마타: 유한 자동화기 (FA)
2. 문맥 자유 언어
   • 문법: 문맥 자유 문법 (Type-2)
   • 오토마타: 푸시다운 자동화기 (PDA)
3. 문맥 민감 언어
   • 문법: 문맥 민감 문법 (Type-1)
   • 오토마타: 선형 제한 자동화기 (LBA)
4. 재귀 열거 언어
   • 문법: 재귀 열거 문법 (Type-0)
   • 오토마타: 튜링 기계 (TM)

---

문법

문법은 규칙들의 모음으로, 형식 언어에서 문자열을 생성하거나 해석하는 데 사용됩니다. 문법은 다음과 같은 요소로 구성됩니다:

• 터미널(Terminal): 언어를 구성하는 기본 기호.
• 비터미널(Non-terminal): 문자열 생성 과정에서 중간 상태로 사용되는 기호.
• 생성 규칙(Production Rule): 문자열 생성 규칙.
• 시작 심볼(Start Symbol): 문자열 생성이 시작되는 초기 상태.

---

문법 규칙 정의 예시

아래는 특정 언어(예: C 프로그래밍 언어의 변수 선언)의 문법 규칙 예시입니다:

1. 시작 심볼(S)에서 시작
2. 문자열 생성
3. S → D V ; D → int | float | ... V → ID | ID, V ID → 식별자명

구문 확인 과정

입력: int a, b;
문법 규칙을 통해 다음과 같이 파생됩니다:

• S → D V ;
• D → int
• V → ID , V
• ID → a
• V → ID
• ID → b

컴파일러는 이러한 파생 과정을 통해 구문이 문법 규칙에 부합하는지 판단하며, 부합하지 않을 경우 **구문 오류(Syntax Error)**로 처리합니다.

---

문법의 분류

Chomsky 계층에 따라 문법은 다음과 같이 분류됩니다:

• Type-0: 재귀 열거 문법 (모든 계산 가능한 언어를 표현 가능).
• Type-1: 문맥 민감 문법 (문맥에 따라 생성 규칙이 제한됨).
• Type-2: 문맥 자유 문법 (비터미널 하나만 좌변에 허용).
• Type-3: 정규 문법 (간단한 구조, 상태 전이 기반).

---

자동화기란?

자동화기는 형식 언어를 인식하는 수학적 모델로, 특정 입력이 언어에 속하는지 판단합니다. 자동화기의 주요 기능:

• 입력이 유효한 경우: 수락 상태(accepting state)로 이동.
• 입력이 유효하지 않은 경우: 수락 상태에 도달하지 않음.

---

자동화기의 종류

1. 유한 자동화기 (FA):
   • 특징: 가장 간단한 형태, 정규 언어를 인식.
   • 제한: 고정된 상태만 사용, 추가 메모리 없음.
2. 푸시다운 자동화기 (PDA):
   • 특징: 상태 집합 + 1개의 스택 사용.
   • 처리 언어: 문맥 자유 언어.
   • 장점: 스택을 통해 중첩 구조 처리 가능.
3. 선형 제한 자동화기 (LBA):
   • 특징: 입력 길이에 제한된 테이프 사용.
   • 처리 언어: 문맥 민감 언어.
   • 제한: 무한 메모리를 사용할 수 없음.
4. 튜링 기계 (TM):
   • 특징: 상태 집합 + 무한 테이프.
   • 처리 언어: 재귀 열거 언어.
   • 장점: 모든 계산 가능한 문제를 처리 가능.

---

Chomsky 계층 구조

• 포함 관계:
  정규 언어 ⊆ 문맥 자유 언어 ⊆ 문맥 민감 언어 ⊆ 재귀 열거 언어.

---

계산 능력과 효율성

계산능력: 자동화기가 처리할 수 있는 언어의 범위

• 만약 M1과 M2라는 두 자동화기가 있을 때, M1의 인식 능력이 M2보다 작다면, M1의 언어 범위 < M2의 언어 범위, M2가 더 강력한 계산 능력을 가짐.
  효율성: 동일한 문제를 해결할 때 걸리는 시간을 기준으로 평가됨
• 만약 M1과 M2라는 두 자동화기가 동일한 문제 P를 해결한다고 가정할 때, M1이 M2보다 더 짧은 시간 안에 문제를 해결한다면, M1이 더 효율적임.

예를 들어, 튜링 기계는 모든 언어를 처리할 수 있지만, 동일한 문제를 해결하는 데 시간이 오래 걸릴 수도 있음. 반면, 유한 자동화기는 제한된 언어만 처리 가능하지만, 단순한 문제를 매우 빠르게 해결.

---

자동화기의 처리 능력 비교

자동화기 처리 가능한 언어 메모리 구조

유한 자동화기 (FA)	정규 언어	상태 집합만 사용
푸시다운 자동화기 (PDA)	문맥 자유 언어	상태 집합 + 1개의 스택
선형 제한 자동화기 (LBA)	문맥 민감 언어	상태 집합 + 제한된 테이프
튜링 기계 (TM)	재귀 열거 언어	상태 집합 + 무한 테이프

---

결정적 자동화기

• 자동화기가 주어진 입력 심볼에서 오직 하나의 상태로만 이동할 수 있음.
• 즉, 모든 입력 심볼에 대해 단 하나의 전이만 존재
• 입력 심볼마다 정확히 한 상태로 이동
• 전이 함수가 항상 하나의 상태만 반환

비결정적 자동화기

• 자동화기가 주어진 입력 심볼에서 여러 상태로 이동할 수 있음.
• 입력 심볼에 대해 0개, 1개, 또는 여러 개의 전이가 가능.
• 동일한 입력 심볼로 여러 상태에 도달 가능
• 입력 심볼에 따라 전이하지 않을 수도 있음.

비결정적인 경우는 유연하고 구현이 간단하지만 시뮬레이션은 비효율적임. 결정적인 경우는 비결정적인 경우에 비해 직관적이고 효율적임.

정규 언어에서 DFA와 NFA의 표현력

• 표현력: DFA와 NFA는 동일한 표현력을 가짐.
• 이유: 모든 NFA는 DFA로 변환 가능하며, 이를 위해 subset construction algorithm이 사용됨.

문맥 자유 언어에서 DPDA와 NPDA

• NPDA(비결정적 푸시다운 자동화기)는 모든 문맥 자유 언어를 처리할 수 있지만, DPDA(결정적 푸시다운 자동화기)는 일부 문맥 자유 언어를 처리하지 못함.
• 예: L = {a^n b^n c^n | n ≥ 1}은 NPDA로 처리 가능하지만 DPDA로는 불가능.

비결정성과 모호함의 관계

1. 비결정성과 모호함의 차이
   비결정성 (Nondeterminism):
   하나의 입력 심볼에 대해 여러 가능한 전이(transition)가 있는 상태.
   시스템이 "어느 경로를 선택해야 할지 명확히 알 수 없는 상태"를 가짐.
   하지만, 올바른 경로가 하나 이상 존재한다면 결과적으로 수락 여부는 명확함.

모호함 (Ambiguity):
하나의 입력이 여러 동등하게 유효한 해석(parses)을 가질 수 있는 경우.
결과적으로 어떤 해석이 맞는지 명확히 정의되지 않음.

2. 비결정성의 모호함 해결
   비결정적 시스템에서도, 추가적인 제약이나 조건을 통해 모호함 문제를 해결할 수 있어:

자동화기:
비결정적 자동화기(NFA)는 모든 가능한 전이를 병렬적으로 처리하여, 입력 문자열을 수락하는 경로가 하나라도 있다면 이를 수락으로 처리함.
→ 결과는 항상 명확.

비결정성이 모호함을 초래하지 않는 이유
비결정성은 "가능성을 열어둔다"는 의미일 뿐, 입력에 대한 최종 결과는 항상 명확히 판단할 수 있음.
NFA의 경우 모든 경로를 동시에 시뮬레이션하므로 모호함이 발생하지 않음.
비결정성이 문제를 복잡하게 만들긴 하지만, 자동화기의 결과 자체는 애매하지 않음.
모호함은 주로 문법 수준에서 발생하며, 모호하지 않은 문법 설계(Unambiguous Grammar)로 해결 가능.

자동화기의 메모리 상태와 계산 능력

1. 유한 자동화기

• 메모리 구조: 고정된 상태 집합만 가짐. 추가적인 메모리가 없음

2. 푸시다운 자동화기

• 메모리 구조: 상태집합 + 하나의 스택. 스택을 이용해 특정 조건 처리 가능

3. 튜링 기계

• 메모리 구조: 상태집합 + 무한 테이프. 테이프를 왼쪽/오른쪽으로 이동하며 읽기와 쓰기가 가능. 구조적으로 2개의 스택을 사용하는 것과 동일함.

메모리 구조와 계산 능력의 예

1. 유한 자동화기(FA): 단순한 패턴 매칭

• 언어: L1 = {a^n | n ≥ 1} (최소 1개의 a를 포함하는 문자열)
• 예: a, aa, aaa, aaaa 등.
• 처리 방식:
  유한 자동화기는 상태만 사용해서 입력을 읽어.
  1. 처음에는 상태 q0(초기 상태)에 있어.
  2. a를 만나면 상태 q1(수락 상태)로 이동.
  3. 이후 계속 a를 만나면 상태 q1에 머물러.
  4. 최소 1개의 a를 만나면 수락.
• 비유:
  • FA는 계산기를 사용하지 않고, 문자열이 "a로 시작했는지"만 확인하는 단순한 동작을 수행.
  • 추가 메모리 없이도 처리 가능.

2. 푸시다운 자동화기(PDA): 중첩 구조를 처리

• 언어: L2 = {a^n b^n | n ≥ 1} (n개의 a 뒤에 정확히 n개의 b)
• 예: ab, aabb, aaabbb 등.
• 처리 방식:
  PDA는 스택이라는 메모리를 사용해서 a와 b의 개수를 비교해.
  1. 상태 q0에서 시작.
  2. a를 읽을 때마다 스택에 a를 추가(push).
  3. b를 읽을 때마다 스택에서 a를 제거(pop).
  4. 입력 문자열 끝에서 스택이 비어 있으면 유효한 문자열.
• 비유:
  • PDA는 종이를 사용해 숫자를 적고 지우는 계산기처럼 동작해.
    • a를 적고(push), b를 읽을 때마다 하나씩 지움(pop).
  • 스택이 비어 있다면 a와 b의 개수가 같음을 보장.

3. 튜링 기계(TM): 복잡한 비교와 계산 가능

• 언어: L3 = {a^n b^n c^n | n ≥ 1} (n개의 a, b, c가 동일한 수로 등장)
• 예: abc, aabbcc, aaabbbccc 등.
• 처리 방식:
  튜링 기계는 무한 테이프를 사용해 복잡한 조건을 처리해.
  1. 첫 번째 테이프에 a를 하나씩 체크하며 두 번째 테이프에 기록.
  2. b를 읽을 때마다 첫 번째 테이프의 기록을 하나씩 삭제.
  3. c를 읽을 때도 동일하게 체크하며 남은 기록을 삭제.
  4. 모든 기록이 삭제되면 유효한 문자열로 판단.
• 비유:
  • TM은 복잡한 계산기를 가진 로봇처럼 동작해.
    • 첫 번째 칸에서 a, 두 번째 칸에서 b, 세 번째 칸에서 c를 정확히 매칭.
  • 이를 위해 무한한 메모리를 사용할 수 있어.

핵심 비교

자동화기	예제 언어	처리 방식	비유
유한 자동화기 (FA)	a^n	단순한 상태 전이로 최소 1개의 a를 확인.	"패턴만 확인하는 간단한 스캐너"
푸시다운 자동화기 (PDA)	a^n b^n	스택을 이용해 a와 b의 개수를 비교.	"종이에 숫자를 적고 지우는 계산기"
튜링 기계 (TM)	a^n b^n c^n	무한 테이프를 사용해 a, b, c를 순차적으로 비교.	"복잡한 계산기를 가진 로봇"

왜 복잡한 언어일수록 더 강력한 자동화기가 필요한가?

• FA(유한 자동화기):
  상태만 사용하므로, 문자열의 길이나 순서를 비교할 수 없음.
• PDA(푸시다운 자동화기):
  스택으로 a와 b의 개수를 비교할 수 있지만, 세 가지 요소(a, b, c)를 동시에 비교는 불가능.
• TM(튜링 기계):
  무한 테이프를 사용해 복잡한 조건을 모두 처리 가능.