• 푸시다운 오토마타는 일반 문법에 대해 DFA를 설계하는 것과 같은 방식으로 CFG를 구현하는 방법입니다. DFA는 유한한 양의 정보를 기억할 수 있지만 PDA는 무한한 양의 정보를 기억할 수 있습니다.
• 푸시다운 오토마타는 단순히 '외부 스택 메모리'로 보강된 NFA입니다. 스택을 추가하면 푸시다운 오토마타에 후입선출 메모리 관리 기능을 제공하는 데 사용됩니다. 푸시다운 오토마타는 스택에 무한한 양의 정보를 저장할 수 있습니다. 스택에 있는 제한된 양의 정보에 액세스할 수 있습니다. PDA는 요소를 스택 상단으로 푸시하고 스택 상단에서 요소를 팝할 수 있습니다. 요소를 스택으로 읽으려면 맨 위 요소가 튀어 나와 손실되어야 합니다.
• PDA는 FA보다 강력합니다. FA에서 허용되는 모든 언어는 PDA에서도 허용될 수 있습니다. PDA는 FA에서도 허용되지 않는 언어 클래스도 허용합니다. 따라서 PDA는 FA보다 훨씬 우수합니다.

PDA 구성요소:

입력 테이프: 입력 테이프는 여러 셀이나 기호로 나누어져 있습니다. 입력 헤드는 읽기 전용이며 한 번에 한 기호씩 왼쪽에서 오른쪽으로만 이동할 수 있습니다.

유한 제어: 유한 제어에는 읽어야 할 현재 기호를 가리키는 포인터가 있습니다.

스택: 스택은 한쪽 끝에서만 항목을 밀고 제거할 수 있는 구조입니다. 무한한 크기를 가지고 있습니다. PDA에서 스택은 항목을 임시로 저장하는 데 사용됩니다.

PDA의 공식 정의:

PDA는 7가지 구성 요소의 모음으로 정의할 수 있습니다.

큐: 유한한 상태 집합

∑: 입력 세트

씨: 스택에서 푸시 및 팝될 수 있는 스택 기호

q0: 초기 상태

안드로이드 폰 설정 메뉴

와 함께: Γ에 있는 시작 기호.

에프: 최종 상태 세트

디: 현재 상태에서 다음 상태로 이동하는 데 사용되는 매핑 함수입니다.

순간 설명(ID)

ID는 PDA가 입력 문자열을 계산하고 문자열이 허용되거나 거부되는지 결정하는 방법에 대한 비공식 표기법입니다.

순간 설명은 삼중 (q, w, α)입니다. 여기서:

큐 현재 상태를 설명합니다.

~ 안에 나머지 입력을 설명합니다.

C의 표준 입력

ㅏ 왼쪽 상단에 스택 내용이 설명되어 있습니다.

개찰구 표기법:

⊢ 기호는 개찰구 표기법을 설명하고 한 번의 이동을 나타냅니다.

⊢* 기호는 일련의 동작을 나타냅니다.

예를 들어,

(p, b, T) ⊢ (q, w, α)

위의 예에서는 상태 p에서 q로 전환하는 동안 입력 기호 'b'가 소비되고 스택 'T'의 최상위는 새로운 문자열 α로 표시됩니다.

예시 1:

언어를 수용하기 위한 PDA 설계^N비²ⁿ.

해결책: 이 언어에서는 n개의 a 다음에 2n개의 b가 와야 합니다. 따라서 우리는 매우 간단한 논리를 적용할 것입니다. 즉, 단일 'a'를 읽으면 두 개의 a를 스택에 푸시합니다. 'b'를 읽자마자 모든 'b'에 대해 단 하나의 'a'만 스택에서 팝되어야 합니다.

ID는 다음과 같이 구성될 수 있습니다.

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) 

이제 b를 읽으면 상태를 q0에서 q1로 변경하고 해당 'a'를 팝하기 시작합니다. 따라서,

 δ(q0, b, a) = (q1, ε) 

따라서 모든 기호를 읽지 않는 한 'b'를 터뜨리는 과정이 반복됩니다. 팝핑 동작은 q1 상태에서만 발생합니다.

자바는 그렇지 않다

 δ(q1, b, a) = (q1, ε) 

모든 b를 읽은 후에는 해당하는 a가 모두 표시되어야 합니다. 따라서 ε을 입력 기호로 읽으면 스택에 아무것도 없어야 합니다. 따라서 이동은 다음과 같습니다.

 δ(q1, ε, Z) = (q2, ε) 

어디

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

ID를 다음과 같이 요약할 수 있습니다.

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε) 

이제 입력 문자열 'aaabbbbbbb'에 대해 이 PDA를 시뮬레이션하겠습니다.

자바가 현재 날짜를 가져오는 중

 δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ) ⊢ δ(q0, abbbbbb, aaaaZ) ⊢ δ(q0, bbbbbb, aaaaaaZ) ⊢ δ(q1, bbbbb, aaaaaZ) ⊢ δ(q1, bbbb, aaaaZ) ⊢ δ(q1, bbb, aaaZ) ⊢ δ(q1, bb, aaZ) ⊢ δ(q1, b, aZ) ⊢ δ(q1, ε, Z) ⊢ δ(q2, ε) ACCEPT 

예 2:

언어를 수용하는 PDA 설계 0^N1^중0^N.

해결책: 이 PDA에서는 n개의 0 뒤에 임의의 수의 1이 오고 그 뒤에 n개의 0이 옵니다. 따라서 이러한 PDA 설계 논리는 다음과 같습니다.

처음 0을 만나면 모든 0을 스택에 푸시합니다. 그러면 1을 읽으면 아무것도 하지 마세요. 그런 다음 0을 읽고, 0을 읽을 때마다 스택에서 0을 하나씩 팝합니다.

예를 들어:

이 시나리오는 ID 형식으로 다음과 같이 작성할 수 있습니다.

 δ(q0, 0, Z) = δ(q0, 0Z) δ(q0, 0, 0) = δ(q0, 00) δ(q0, 1, 0) = δ(q1, 0) δ(q0, 1, 0) = δ(q1, 0) δ(q1, 0, 0) = δ(q1, ε) δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state) 

이제 입력 문자열 '0011100'에 대해 이 PDA를 시뮬레이션하겠습니다.

 δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ⊢ δ(q0, 11100, 00Z) ⊢ δ(q0, 1100, 00Z) ⊢ δ(q1, 100, 00Z) ⊢ δ(q1, 00, 00Z) ⊢ δ(q1, 0, 0Z) ⊢ δ(q1, ε, Z) ⊢ δ(q2, Z) ACCEPT