Finite Automaton은 State가 유한하므로 임의의 개수를 기억할 수 없다. Pushdown Automaton(PDA)은 Stack을 추가하여 중첩 구조나 앞부분의 개수를 기억한다. CFG와 같은 Context-Free Language를 다룬다.

구성 요소

한 정의에서 PDA는 다음 7-tuple이다.

  • : State Set
  • : Input Alphabet
  • : Stack Alphabet
  • : Transition Function
  • : Start State
  • : Initial Stack Symbol
  • : Accept State Set

Nondeterministic PDA의 Transition은 현재 State, 입력 Symbol 또는 ε, Stack Top을 받아 가능한 동작의 Set을 반환한다.

Stack Top을 Pop한 뒤 의 String으로 교체한다고 해석하면 Push, Pop, 유지가 모두 표현된다.

Instantaneous Description

PDA의 한 순간을

로 나타낼 수 있다.

  • : 현재 State
  • : 아직 읽지 않은 Input
  • : 현재 Stack Content

한 Transition에 따른 이동을 로 나타낸다.

예제:

전략은 다음과 같다.

  1. 를 읽는 동안 Stack에 Marker 를 Push한다.
  2. 첫 를 읽으면 Pop 단계로 전환한다.
  3. 각 마다 하나를 Pop한다.
  4. Input이 끝나고 Stack이 Initial Symbol만 남으면 Accept한다.

의 Stack 높이는 a를 읽을 때 3까지 증가하고 b를 읽을 때 0으로 감소한다. 순서가 처럼 섞이면 중간에 Transition이 없어 Reject한다.

Final State Acceptance

Input을 모두 읽은 뒤 Accept State에 도달하면 Accept한다.

Stack에 일부 Symbol이 남아 있어도 정의에 따라 Accept할 수 있다.

Empty Stack Acceptance

Input을 모두 읽고 Stack이 비면 Accept한다.

NPDA에서는 Final State Acceptance와 Empty Stack Acceptance가 같은 CFL Class를 정의하며 상호 변환할 수 있다.

Nondeterminism이 필요한 이유

어떤 Language에서는 Input의 어느 지점이 중간인지 미리 알 수 없다. 예를 들어 Palindrome Language에서 PDA는 중간을 Nondeterministically 추측하고 그 전까지 Push한 Symbol과 이후 Input을 비교할 수 있다.

Deterministic PDA는 NPDA보다 표현력이 약하며 모든 CFL을 인식하지 못한다.

정리

  • PDA는 Finite Control과 Stack으로 구성된다.
  • Stack은 LIFO 방식으로 무한한 개수의 정보를 제한된 형태로 저장한다.
  • ID는 State, 남은 Input, Stack Content를 기록한다.
  • NPDA의 Final State Acceptance와 Empty Stack Acceptance는 동등하다.

연습 문제

1번

를 PDA가 처리할 때 Stack Content의 변화를 순서대로 적는다. Initial Stack Symbol은 이다.

2번

Finite Automaton만으로 을 인식하기 어려운 이유와 PDA의 Stack이 해결하는 정보를 설명한다.

풀이

1번

입력 a를 읽을 때 Marker를 Push하고 b를 읽을 때 Pop한다.

Input이 끝났고 Marker가 모두 제거되므로 Accept한다.

2번

DFA는 앞의 a 개수를 무한히 구분할 State를 가질 수 없다. PDA는 각 a마다 Stack Symbol을 Push하여 개수를 저장하고, b마다 하나씩 Pop하여 두 개수가 같은지 확인한다.