언어 "L"이 주어졌을 때, 우리의 과제는 이 언어에 대한 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것입니다. 이 언어는 문자 'a'의 등장 횟수가 문자 'b'의 등장 횟수의 정확히 두 배이고, 문자 'c'의 등장 횟수가 문자 'd'의 등장 횟수의 정확히 네 배여야 함을 의미합니다. 또한 모든 문자의 최소 등장 횟수는 1회이지만, 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, δ, q0, I, F)로 기술할 수 있습니다.
- Q : 유한 개수의 상태 집합
- Σ : 입력 알파벳
- S : 스택 심볼
- δ : 전이 함수 — Q × (Σ ∪ {ε}) × S → Q × S*
- q0 : 초기 상태 (q0 ∈ Q)
- I : 초기 스택 최상단 심볼 (I ∈ S)
- F : accepting 상태의 집합 (F ⊆ Q)
주어진 언어에 대한 푸시다운 오토마타 구성
이 PDA가 받아들일 수 있는 문자열은 다음과 같은 형태입니다.
- c⁴ⁿdⁿ 형태 — ccccd, ccccccccdd 등. c의 개수가 d의 개수의 4배입니다. m이 0이면 a와 b는 존재하지 않습니다. c들을 계속 스택에 push하다가 첫 번째 d를 만나면 스택에서 c 4개를 pop합니다. 문자열의 끝에 도달했을 때 스택에 남은 c가 없다면 해당 문자열은 accepted입니다.
- a²ᵐbᵐ 형태 — aab, aaaabb 등. a의 개수가 b의 개수의 2배입니다. n이 0이면 c와 d는 존재하지 않습니다. a들을 계속 스택에 push하다가 첫 번째 b를 만나면 스택에서 a 2개를 pop합니다. 문자열의 끝에 도달했을 때 스택에 남은 a가 없다면 해당 문자열은 accepted입니다.
- a²ᵐc⁴ⁿdⁿbᵐ 형태 — aaccccdb, aaaaccccccccddbb 등. a의 개수는 b의 개수의 2배이고, c의 개수는 d의 개수의 4배입니다. a와 c를 계속 push하다가 첫 번째 d를 만나면 스택 최상단에 있는 c 4개를 pop하고, 이후 나머지 b들에 대해서는 a 2개씩 pop합니다. 문자열 끝에 도달했을 때 스택에 남은 a가 없다면 accepted입니다.
- NULL 문자열 역시 accepted입니다. 즉, a⁰c⁰d⁰b⁰의 경우입니다.
오토마타 동작 원리 살펴보기
q0 상태의 전이 규칙
- ( a, I/a,I ) — 스택 최상단이 I이고 현재 입력 심볼이 a이면, a를 스택 최상단에 push하고 q0에 머무릅니다. 스택은 aI…가 됩니다.
- ( c, I/c,I ) — 스택 최상단이 I이고 현재 입력 심볼이 c이면, c를 스택 최상단에 push하고 q0에 머무릅니다. 스택은 cI…가 됩니다.
- ( a, a/a,a ) — 스택 최상단이 a이고 현재 입력 심볼도 a이면, a를 스택 최상단에 push하고 q0에 머무릅니다. 스택은 aa…가 됩니다. 다음에 c나 b가 나올 때까지 a를 계속 push합니다.
- ( c, c/c,c ) — 스택 최상단이 c이고 현재 입력 심볼도 c이면, c를 스택 최상단에 push하고 q0에 머무릅니다. 스택은 cc…가 됩니다. 다음 d가 나올 때까지 c를 계속 push합니다.
- ( b, a/e,aa ) — 스택 최상단이 a이고 현재 입력 심볼이 b이면, 스택에서 a 2개를 pop하고 q3으로 이동합니다.
- ( c, a/c,a ) — 스택 최상단이 a이고 현재 입력 심볼이 c이면, c를 스택 최상단에 push하고 q1으로 이동합니다. 스택은 ca…가 됩니다.
- ( d, c/e,cccc ) — 스택 최상단이 c이고 현재 입력 심볼이 d이면, 스택에서 c 4개를 pop하고 q4로 이동합니다.
- ( $, I/I,I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q5로 이동합니다. NULL 문자열을 위한 규칙입니다.
q1 상태의 전이 규칙
- ( c, c/c,c ) — 스택 최상단이 c이고 현재 입력 심볼도 c이면, c를 스택 최상단에 push하고 q1에 머무릅니다. 스택은 cc…가 됩니다. 다음 d가 나올 때까지 c를 계속 push합니다.
- ( d, c/e,cccc ) — 스택 최상단이 c이고 현재 입력 심볼이 d이면, 스택에서 c 4개를 pop하고 q2로 이동합니다.
q2 상태의 전이 규칙
- ( d, c/e,cccc ) — 스택 최상단이 c이고 현재 입력 심볼이 d이면, 스택에서 c 4개를 pop하고 q2에 머무릅니다.
- ( b, a/e,aa ) — 스택 최상단이 a이고 현재 입력 심볼이 b이면, 스택에서 a 2개를 pop하고 q3으로 이동합니다.
q3 상태의 전이 규칙
- ( b, a/e,aa ) — 스택 최상단이 a이고 현재 입력 심볼이 b이면, 스택에서 a 2개를 pop하고 q3에 머무릅니다.
- ( $, I/I,I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q5로 이동합니다.
q4 상태의 전이 규칙
- ( d, c/e,cccc ) — 스택 최상단이 c이고 현재 입력 심볼이 d이면, 스택에서 c 4개를 pop하고 q4에 머무릅니다.
- ( $, I/I,I ) — 스택 최상단이 I이고 더 이상 입력이 없으면 아무 작업도 하지 않고 q5로 이동합니다.