언어 "L"이 주어지고 작업은 0의 발생이 1과 2의 발생을 더할 것임을 설명하는 주어진 언어에 대한 푸시다운 오토마타를 구성하는 것입니다. 또한 1과 2의 발생은 문자열을 NULL로 만들 수 있는 최소 하나가 될 것이며 자동 장치에서 이를 수락해야 합니다.
푸시다운 Automata란 무엇입니까?
푸시다운 오토마타 또는 푸시다운 오토마톤 또는 PDA는 일반 문법에 대해 Deterministic Finite Automaton 또는 DFA를 설계하는 것과 유사한 방식으로 문맥 없는 문법을 구현하는 기술입니다. DFA는 유한 데이터에서 작동할 수 있지만 PDA는 무한 데이터에서 작동할 수 있습니다. 푸시다운 오토마타는 "유한 상태 기계"와 "스택"의 조합으로 이해할 수 있습니다.
푸시다운 자동 장치에는 세 가지 구성 요소가 있습니다.
-
입력 테이프,
-
제어 장치 및
-
무한한 크기의 스택입니다.
PDA는 공식적으로 7-튜플(Q, Ʃ, S, δ, q0, I, F) -
으로 설명될 수 있습니다.-
Q는 유한 상태의 수입니다.
-
Ʃ는 알파벳 입력
-
S는 스택 기호입니다.
-
δ는 전이 함수입니다. Q × (Ʃ υ {ε}) × S × Q × S*
-
q0은 초기 상태입니다(q0 ε Q)
-
I는 초기 스택 상단 기호입니다(I ε S)
-
F는 수용 상태의 집합입니다(F ε Q)
주어진 언어에 대한 푸시다운 Automata를 구성해 봅시다. -
이 PDA에서 허용되는 문자열은 -
형식입니다.-
1. 0 n 2 n :02, 0022, 000222 등. 0의 숫자는 0과 같습니다. 2초의. m이 0이면 1이 없습니다. 계속 0을 누르고 처음 2를 만나면 0을 팝니다. 문자열 끝에 도달했는데 0이 없으면 문자열이 허용됩니다.
-
0 분 1 분 :01, 0011, 000111 등. 0의 번호는 아니오와 같습니다. 1초. n이 0이면 2가 없습니다. 0을 계속 누르고 첫 번째 1이 발생하자마자 0을 팝니다. 문자열 끝에 도달했는데 0이 없으면 문자열이 허용됩니다.
-
0 n+m 1 분 2 n :0012, 000112, 000122 등. 0의 개수는 숫자의 합과 같습니다. 1초와 2초. 0을 계속 누르고 처음 1이 나타나면 1이 남지 않을 때까지 0을 팝합니다. 그런 다음 0을 계속 누르고 처음 2가 나타나면 2가 남지 않을 때까지 0을 팝합니다. 문자열이 허용됩니다.
-
NULL 문자열도 허용됩니다. 0 0 1 0 2 0
기계를 이해하자
-
상태 q0에 대한 전환:
-
0, I/0I ) - 스택의 맨 위가 I이고 현재 입력 기호가 0이면 스택의 맨 위로 0을 누르고 q0을 유지합니다. 스택이 0I가 됩니다...
-
( 0, 0/00 ) - 스택의 맨 위가 0이고 현재 입력 기호도 0이면 0을 스택 맨 위로 푸시하고 q0에 유지합니다. 스택이 00이 됩니다.... 다음 1 또는 2가 될 때까지 0을 계속 누릅니다.
-
( 1, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 0을 팝하고 q1로 이동합니다.
-
( 2, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 2이면 0을 팝하고 q2로 이동합니다.
-
( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 qf로 이동합니다. NULL 문자열의 경우.
-
-
상태 q1 −
에 대한 전환-
( 1, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 0을 팝하고 q1에 유지합니다.
-
( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 qf로 이동합니다.
-
( 2, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 2이면 0을 팝하고 q2로 이동합니다.
-
-
상태 q2 −
에 대한 전환-
( 2, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 2이면 0을 팝하고 q2에 남습니다.
-
($, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 qf로 이동합니다.
-