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

주어진 언어 "L"에 대해 푸시다운 오토마타(Pushdown Automata)를 구성하는 것이 목표입니다. 이 언어에서는 0의 개수가 1의 개수와 2의 개수의 합과 같아야 하며, 1과 2는 각각 최소 한 번 이상 나타나거나 문자열이 NULL(빈 문자열)일 수도 있습니다. 이러한 모든 문자열은 오토마타에 의해 수용되어야 합니다.

푸시다운 오토마타란?

푸시다운 오토마타(PDA)는 정규 문법을 위해 결정적 유한 오토마타(DFA)를 설계하는 것과 유사한 방식으로 문맥 무관 문법(Context-Free Grammar)을 구현하는 기법입니다. DFA는 유한한 데이터만 처리할 수 있지만, PDA는 무한한 데이터도 처리할 수 있습니다. 푸시다운 오토마타는 "유한 상태 머신(finite state machine)"과 "스택(stack)"의 조합으로 이해할 수 있습니다.

푸시다운 오토마타는 세 가지 구성 요소로 이루어집니다.

• 입력 테이프(input tape)
• 제어 장치(control unit)
• 무한 크기의 스택(stack)

PDA는 공식적으로 7-튜플(Q, Ʃ, S, δ, q0, I, F)로 표현됩니다.

• Q: 유한한 개수의 상태 집합
• Ʃ: 입력 알파벳
• S: 스택 심볼
• δ: 전이 함수 — Q × (Ʃ ∪ {ε}) × S × Q × S*
• q0: 시작 상태 (q0 ∈ Q)
• I: 초기 스택 최상위 심볼 (I ∈ S)
• F: 수용 상태의 집합 (F ⊆ Q)

주어진 언어에 대한 푸시다운 오토마타 구성하기

이 PDA가 수용하는 문자열은 다음과 같은 형태입니다.

• 0ⁿ2ⁿ : 02, 0022, 000222 등. 0의 개수와 2의 개수가 같습니다. m이 0이면 1은 존재하지 않습니다. 0을 계속 스택에 push하다가 첫 번째 2를 만나면 0을 pop합니다. 문자열의 끝에 도달했을 때 스택에 남은 0이 없다면 해당 문자열은 수용됩니다.
• 0^m1^m : 01, 0011, 000111 등. 0의 개수와 1의 개수가 같습니다. n이 0이면 2는 존재하지 않습니다. 0을 계속 push하다가 첫 번째 1을 만나면 0을 pop합니다. 문자열의 끝에 도달했을 때 스택에 남은 0이 없다면 해당 문자열은 수용됩니다.
• 0^n+m1^m2ⁿ : 0012, 000112, 000122 등. 0의 개수가 1의 개수와 2의 개수의 합과 같습니다. 0을 계속 push하다가 첫 번째 1을 만나면 1이 모두 소진될 때까지 0을 pop합니다. 이후 다시 0을 push하고, 첫 번째 2를 만나면 2가 모두 소진될 때까지 0을 pop합니다. 이렇게 하면 문자열이 수용됩니다.
• NULL 문자열도 수용됩니다. 즉, 0⁰1⁰2⁰ = ε 입니다.

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

상태 q0의 전이 규칙

• (0, I/0I) : 스택 최상위가 I이고 현재 입력 심볼이 0이면 0을 스택에 push하고 q0에 머무릅니다. 스택은 0I...가 됩니다.
• (0, 0/00) : 스택 최상위가 0이고 현재 입력 심볼도 0이면 0을 스택에 push하고 q0에 머무릅니다. 스택은 00...이 됩니다. 다음 1 또는 2가 나올 때까지 0을 계속 push합니다.
• (1, 0/$) : 스택 최상위가 0이고 현재 입력 심볼이 1이면 0을 pop하고 q1으로 이동합니다.
• (2, 0/$) : 스택 최상위가 0이고 현재 입력 심볼이 2이면 0을 pop하고 q2로 이동합니다.
• ($, I/I) : 스택 최상위가 I이고 더 이상 입력이 없으면 아무 작업도 수행하지 않고 qf로 이동합니다. NULL 문자열을 처리하기 위한 규칙입니다.

상태 q1의 전이 규칙

• (1, 0/$) : 스택 최상위가 0이고 현재 입력 심볼이 1이면 0을 pop하고 q1에 머무릅니다.
• ($, I/I) : 스택 최상위가 I이고 더 이상 입력이 없으면 아무 작업도 수행하지 않고 qf로 이동합니다.
• (2, 0/$) : 스택 최상위가 0이고 현재 입력 심볼이 2이면 0을 pop하고 q2로 이동합니다.

상태 q2의 전이 규칙

• (2, 0/$) : 스택 최상위가 0이고 현재 입력 심볼이 2이면 0을 pop하고 q2에 머무릅니다.
• ($, I/I) : 스택 최상위가 I이고 더 이상 입력이 없으면 아무 작업도 수행하지 않고 qf로 이동합니다.