L = {0ⁿ1ᵐ2ᵐ3ⁿ | m, n ≥ 0} 언어를 위한 푸시다운 오토마타(PDA) 구성

언어 L = {0ⁿ1^m2^m3ⁿ | m, n ≥ 0}가 주어졌을 때, 이 언어를 인식하는 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것이 과제입니다. 이 언어에서는 0의 개수와 3의 개수가 같아야 하고, 1의 개수와 2의 개수가 같아야 합니다. 또한 지수 m과 n은 0 이상이므로, 모든 숫자가 한 번 이상 나타나야 하는 것은 아니며 빈 문자열(NULL) 역시 유효한 문자열로서 오토마타에 의해 수용되어야 합니다.

푸시다운 오토마타란 무엇인가?

푸시다운 오토마타(PDA)는 정규 문법(regular grammar)에 대해 결정적 유한 오토마타(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: 수용 상태(accepting state)들의 집합 (F ⊆ Q)

주어진 언어를 위한 푸시다운 오토마타 구성

이 PDA가 수용할 수 있는 문자열의 형태는 다음과 같습니다.

• 0ⁿ3ⁿ — 03, 0033, 000333 등. 0의 개수와 3의 개수가 같습니다. m이 0이면 1과 2는 나타나지 않습니다. 0을 스택에 계속 쌓다가(push) 처음으로 3을 만나면 스택에서 0을 하나씩 꺼내고(pop), 문자열의 끝에 도달했을 때 스택에 0이 남아 있지 않으면 문자열을 수용합니다.
• 1^m2^m — 12, 1122, 111222 등. 1의 개수와 2의 개수가 같습니다. n이 0이면 0과 3은 나타나지 않습니다. 1을 계속 쌓다가 처음으로 2를 만나면 1을 꺼내고, 문자열의 끝에 도달했을 때 스택에 1이 남아 있지 않으면 문자열을 수용합니다.
• 0ⁿ1^m2^m3ⁿ — 0123, 001233, 011223 등. 0의 개수와 3의 개수가 같고, 1의 개수와 2의 개수가 같습니다. 0과 1을 계속 쌓다가 처음으로 2를 만나면 스택 최상단의 1부터 꺼내고, 이후 3에 대해서는 0을 꺼냅니다. 문자열의 끝에 도달했을 때 스택에 0이 남아 있지 않으면 문자열을 수용합니다.
• NULL 문자열 역시 수용됩니다. 즉, 0⁰1⁰2⁰3⁰인 경우입니다.

오토마타 동작 원리 이해하기

상태 q0의 전이 규칙

• ( 0, I/0I ) — 스택 최상단이 I이고 현재 입력 기호가 0이면, 0을 스택에 쌓고 q0에 머무릅니다. 스택은 0I...가 됩니다.
• ( 0, 0/00 ) — 스택 최상단이 0이고 현재 입력 기호도 0이면, 0을 스택에 쌓고 q0에 머무릅니다. 스택은 00...이 됩니다. 다음 입력이 1 또는 3이 올 때까지 0을 계속 쌓습니다.
• ( 1, 0/10 ) — 스택 최상단이 0이고 현재 입력 기호가 1이면, 1을 스택에 쌓고 q1으로 이동합니다. 스택은 10...이 됩니다.
• ( 1, I/1I ) — 스택 최상단이 I이고 현재 입력 기호가 1이면, 1을 쌓고 q5로 이동합니다.
• ( 3, 0/ε ) — 스택 최상단이 0이고 현재 입력 기호가 3이면, 0을 꺼내고 q3으로 이동합니다.
• ( $, I/I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q4로 이동합니다. NULL 문자열 처리를 위한 규칙입니다.

상태 q1의 전이 규칙

• ( 1, 1/11 ) — 스택 최상단이 1이고 현재 입력 기호도 1이면, 1을 스택에 쌓고 q1에 머무릅니다. 스택은 11...이 됩니다. 다음 입력이 2가 올 때까지 1을 계속 쌓습니다.
• ( 2, 1/ε ) — 스택 최상단이 1이고 현재 입력 기호가 2이면, 1을 꺼내고 q2로 이동합니다.

상태 q2의 전이 규칙

• ( 2, 1/ε ) — 스택 최상단이 1이고 현재 입력 기호가 2이면, 1을 꺼내고 q2에 머무릅니다.
• ( 3, 0/ε ) — 스택 최상단이 0이고 현재 입력 기호가 3이면, 0을 꺼내고 q3으로 이동합니다.

상태 q3의 전이 규칙

• ( 3, 0/ε ) — 스택 최상단이 0이고 현재 입력 기호가 3이면, 0을 꺼내고 q3에 머무릅니다.
• ( $, I/I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q4로 이동합니다. NULL 문자열 처리를 위한 규칙입니다.

상태 q5의 전이 규칙

• ( 1, 1/11 ) — 스택 최상단이 1이고 현재 입력 기호도 1이면, 1을 스택에 쌓고 q5에 머무릅니다. 스택은 11...이 됩니다. 다음 입력이 2가 올 때까지 1을 계속 쌓습니다.
• ( 2, 1/ε ) — 스택 최상단이 1이고 현재 입력 기호가 2이면, 1을 꺼내고 q6으로 이동합니다.

상태 q6의 전이 규칙

• ( 2, 1/ε ) — 스택 최상단이 1이고 현재 입력 기호가 2이면, 1을 꺼내고 q6에 머무릅니다.
• ( $, I/I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q4로 이동합니다. NULL 문자열 처리를 위한 규칙입니다.

이처럼 각 상태에서 스택의 최상단 기호와 입력 기호를 비교하여 push 또는 pop 연산을 수행함으로써, 0과 3의 개수 그리고 1과 2의 개수가 각각 일치하는지를 검증할 수 있습니다. 모든 입력을 소진하고 스택이 초기 기호 I만 남았을 때 최종 상태(q4)에 도달하면 해당 문자열은 언어 L에 속하는 것으로 수용됩니다.