언어 "L"이 주어지고 작업은 0과 3의 발생이 동일하고 1의 발생과 1의 발생을 설명하는 주어진 언어에 대한 푸시다운 오토마타를 구성하는 것입니다. 2는 같을 것이고 모든 숫자의 출현은 최소 1이어야 문자열을 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에서 허용되는 문자열은 -
형식입니다.-
0 n 3 n − 03, 0033, 000333 등. 0의 수는 아니오와 같습니다. 3초. m이 0이면 1과 2가 없습니다. 0을 계속 누르고 처음 3이 발생하자마자 0을 팝니다. 문자열 끝에 도달했는데 0이 없으면 문자열이 허용됩니다.
-
1 분 2 분 − 12, 1122, 111222 등. 1의 수는 아니오와 같습니다. 2초의. n이 0이면 0과 3이 없습니다. 1을 계속 누르고 처음 2가 발생하자마자 1을 팝니다. 문자열 끝에 도달하고 1이 없으면 문자열이 허용됩니다.
-
0 n 1 분 2 분 3 n − 0123, 001233, 011223 등. 0의 번호는 아니오와 같습니다. 3과 1은 2와 같습니다. 0과 1을 계속 누르십시오. 처음 2가 발생하자마자 맨 위에 있으면 1을 팝하고 나머지 3에 대해서는 0을 팝합니다. 끝에 도달하고 0이 남지 않으면 문자열이 허용됩니다.
-
NULL 문자열도 허용됩니다. 0 0 1 0 2 0 3 0 .
기계를 이해하자
-
상태 q0 −
에 대한 전환-
( 0, I/0,I ) - 스택의 맨 위가 I이고 현재 입력 기호가 0이면 스택 맨 위로 0을 누르고 q0에 유지합니다. 스택이 0I가 됩니다...
-
( 0, 0/0,0 ) - 스택의 맨 위가 0이고 현재 입력 기호도 0이면 0을 스택 맨 위로 푸시하고 q0에 유지합니다. 스택이 00이 됩니다.... 다음 1 또는 3이 될 때까지 0을 계속 누릅니다.
-
( 1, 0/1,0 ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 스택 맨 위로 1을 누르고 q1로 이동합니다. 스택이 10이 됩니다...
-
( 1, I/1,I ) - 스택의 맨 위가 I이고 현재 입력 기호가 1이면 1을 누르고 q5로 이동합니다.
-
( 3, 0/e ) - 스택의 맨 위가 0이고 현재 입력 기호가 3이면 0을 팝하고 q3으로 이동합니다.
-
( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q4로 이동합니다. NULL 문자열의 경우.
-
-
상태 q1 −
에 대한 전환-
( 1, 1/11 ) - 스택의 맨 위가 1이고 현재 입력 기호도 1이면 1을 스택 맨 위로 푸시하고 q1에 유지합니다. 스택은 11이 됩니다.... 다음 2까지 1을 계속 누르십시오.
-
( 2, 1/e ) - 스택의 맨 위가 1이고 현재 입력 심볼이 2이면 1을 팝하고 q2로 이동합니다.
-
-
상태 q2 −
에 대한 전환-
( 2, 1/e ) - 스택의 맨 위가 1이고 현재 입력 기호가 2이면 1을 팝하고 q2에 남습니다.
-
( 3, 0/e ) - 스택의 맨 위가 0이고 현재 입력 기호가 3이면 0을 팝하고 q3으로 이동합니다.
-
-
상태 q3 −
에 대한 전환-
( 3, 0/e ) - 스택의 맨 위가 0이고 현재 입력 기호가 3이면 1을 팝하고 q3에 남아 있습니다.
-
( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q4로 이동합니다. NULL 문자열의 경우.
-
-
상태 q5 −
에 대한 전환-
( 1, 1/1,1 ) - 스택의 맨 위가 1이고 현재 입력 기호도 1이면 스택 맨 위로 1을 누르고 q5에 유지합니다. 스택은 11이 됩니다.... 다음 2까지 1을 계속 누르십시오.
-
( 2, 1/e ) - 스택의 맨 위가 1이고 현재 입력 기호가 2이면 1을 팝하고 q6으로 이동합니다.
-
-
상태 q6 −
에 대한 전환-
( 2, 1/e ) - 스택의 맨 위가 1이고 현재 입력 기호가 2이면 1을 팝하고 q6에 남습니다.
-
( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q4로 이동합니다. NULL 문자열의 경우.
-