언어 "L"이 주어졌을 때, 해당 언어에 대한 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것이 목표입니다. 이 언어에서 1의 개수는 0의 개수와 2의 개수를 더한 값과 같아야 하며, 0과 2는 최소 한 번씩 나타나거나 문자열이 NULL(빈 문자열)일 수도 있습니다. 빈 문자열 역시 오토마타가 수용해야 합니다.
푸시다운 오토마타란?
푸시다운 오토마타(PDA)는 정규 문법을 위해 결정적 유한 오토마타(DFA)를 설계하는 방식과 유사하게, 문맥 자유 문법(context-free grammar)을 구현하는 기법입니다. DFA는 유한한 데이터만 처리할 수 있는 반면, PDA는 무한한 데이터도 처리할 수 있습니다. 푸시다운 오토마타는 "유한 상태 머신(finite state machine)"과 "스택(stack)"의 결합으로 이해할 수 있습니다.
푸시다운 오토마타는 세 가지 구성 요소로 이루어져 있습니다.
- 입력 테이프(input tape)
- 제어 유닛(control unit)
- 무한 크기의 스택(stack)
PDA는 공식적으로 7-튜플 (Q, Σ, S, δ, q₀, I, F)로 표현됩니다.
- Q: 유한 개수의 상태 집합
- Σ: 입력 알파벳
- S: 스택 심볼의 집합
- δ: 전이 함수 : Q × (Σ ∪ {ε}) × S → Q × S*
- q₀: 초기 상태 (q₀ ∈ Q)
- I: 초기 스택 최상위 심볼 (I ∈ S)
- F: 수용 상태의 집합 (F ⊆ Q)
주어진 언어에 대한 PDA 구성
이 PDA가 수용할 수 있는 문자열의 형태는 다음과 같습니다.
- 0m1m — 01, 0011, 000111 등. 0의 개수와 1의 개수가 같은 경우입니다. n이 0이면 2는 존재하지 않습니다. 0을 계속 스택에 쌓다가(push) 첫 번째 1을 만나면 0을 하나씩 꺼내고(pop), 문자열 끝에 도달했을 때 스택에 남은 0이 없다면 문자열이 수용됩니다.
- 1n2n — 12, 1122, 111222 등. 1의 개수와 2의 개수가 같은 경우입니다. m이 0이면 0은 존재하지 않습니다. 1을 계속 스택에 쌓다가 첫 번째 2를 만나면 1을 하나씩 꺼내고, 문자열 끝에 도달했을 때 스택에 남은 1이 없다면 문자열이 수용됩니다.
- 0n1m+n2m — 0112, 001112 등. 1의 개수가 0의 개수와 2의 개수의 합과 같은 경우입니다. 0을 계속 스택에 쌓다가 첫 번째 1을 만나면 0이 모두 소진될 때까지 0을 꺼냅니다. 이후 다시 1을 스택에 쌓다가 첫 번째 2를 만나면, 각 2마다 1을 하나씩 꺼내어 1이 모두 소진될 때까지 반복합니다. 문자열 끝에 도달했을 때 남은 1이 없다면 문자열이 수용됩니다.
- NULL 문자열도 수용됩니다. 즉, 001020인 빈 문자열입니다.
머신 동작 상세 이해
- 상태 q0의 전이 규칙
- (0, I/0I) — 스택 최상위가 I이고 현재 입력 심볼이 0이면, 0을 스택에 쌓고(push) q0에 머무릅니다. 스택은 0I... 형태가 됩니다.
- (0, 0/00) — 스택 최상위가 0이고 현재 입력 심볼도 0이면, 0을 스택에 쌓고 q0에 머무릅니다. 스택은 00... 형태가 되며, 다음 1 또는 2가 나올 때까지 0을 계속 쌓습니다.
- (1, I/1I) — 스택 최상위가 I이고 현재 입력 심볼이 1이면, 1을 스택에 쌓고 q1으로 이동합니다. 스택은 1I... 형태가 됩니다.
- (1, 0/$) — 스택 최상위가 0이고 현재 입력 심볼이 1이면, 0을 꺼내고(pop) q1으로 이동합니다.
- 상태 q1의 전이 규칙
- (1, 1/11) — 스택 최상위가 1이고 현재 입력 심볼도 1이면, 1을 스택에 쌓고 q1에 머무릅니다. 스택은 11... 형태가 되며, 다음 0 또는 2가 나올 때까지 1을 계속 쌓습니다.
- (1, 0/$) — 스택 최상위가 0이고 현재 입력 심볼이 1이면, 0을 꺼내고 q1에 머무릅니다.
- ($, I/I) — 스택 최상위가 I이고 더 이상 입력이 없으면, 아무 작업도 수행하지 않고 최종 상태 qf로 이동합니다.
- (2, 1/$) — 스택 최상위가 1이고 현재 입력 심볼이 2이면, 1을 꺼내고 q2로 이동합니다.
- 상태 q2의 전이 규칙
- (2, 1/$) — 스택 최상위가 1이고 현재 입력 심볼이 2이면, 1을 꺼내고 q2에 머무릅니다.
- ($, I/I) — 스택 최상위가 I이고 더 이상 입력이 없으면, 아무 작업도 수행하지 않고 최종 상태 qf로 이동합니다.
이처럼 세 개의 상태(q0, q1, q2)와 스택 연산(push/pop)을 조합하면, 1의 개수가 0과 2의 개수의 합과 일치하는 모든 문자열을 정확히 판별하는 푸시다운 오토마타를 완성할 수 있습니다.