우리에게는 "L"이라는 언어가 주어지며, 과제는 주어진 언어에 대해 'a' 문자가 발생하는 시간이 두 배로 발생해야 한다고 설명하는 푸시다운 오토마타를 구성하는 것입니다. 문자 'b'와 문자 'c'의 발생 횟수는 'd'의 4배여야 하며 모든 문자의 발생 횟수는 최소 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에서 허용되는 문자열은 -
형식입니다.-
c 4n d n - ccccd, ccccccccdd 등. cs 수는 4번입니다. 의 ds. m이 0이면 as와 bs가 없습니다. cs를 계속 누르고 첫 번째 d가 발생하자마자 스택에서 4 c를 꺼냅니다. 문자열 끝에 도달했는데 cs가 없으면 문자열이 허용됩니다.
-
2m b m - aab, aaaabb 등 as의 개수는 no의 2배입니다. 의 bs. n이 0이면 cs와 ds가 없습니다. 첫 번째 b가 발생하는 즉시 계속 누르고 스택에서 2b를 꺼냅니다. 문자열의 끝에 도달했는데 as가 없으면 문자열이 허용됩니다.
-
2m c 4n d n b m - aaccccdb, aaaaccccccccddbb. 그대로의 수는 아니오의 2배입니다. bs 및 cs의 수는 ds 수의 4배입니다. as 및 cs를 계속 누릅니다. 첫 번째 d가 발생하자마자 맨 위에 있으면 4개 cs를 팝하고 나머지 bs에 대해서는 2개를 팝니다. 끝에 도달하고 아무 것도 남지 않으면 문자열이 허용됩니다.
-
NULL 문자열도 허용됩니다. a 0 c 0 d 0 b 0 .
기계를 이해하자
-
상태 q0 −
에 대한 전환-
( a, I/a,I ) - 스택의 맨 위가 I이고 현재 입력 기호가 a이면 a를 스택 맨 위로 밀어 q0에 유지합니다. 스택이 AI가 됩니다...
-
( c, I/c,I ) - 스택의 맨 위가 I이고 현재 입력 기호가 c이면 c를 스택 맨 위로 푸시하고 q0에 유지합니다. 스택은 CI가 됩니다...
-
( a, a/a,a ) - 스택 맨 위가 a이고 현재 입력 기호도 a이면 a를 스택 맨 위로 푸시하고 q0에 유지합니다. 스택은 aa가 됩니다.... 다음 c 또는 b까지 계속 푸시합니다.
-
( c, c/c,c ) - 스택의 맨 위가 c이고 현재 입력 기호도 c이면 c를 스택 맨 위로 푸시하고 q0에 유지합니다. 스택이 cc가 됩니다.... 다음 d까지 cs를 계속 푸시합니다.
-
( b, a/e,aa ) - 스택의 맨 위가 a이고 현재 입력 기호가 b이면 스택에서 2를 팝하고 q3으로 이동합니다.
-
(c, a/c,a ) - 스택의 맨 위가 a이고 현재 입력 기호가 c이면 c를 스택 맨 위로 밀어 q1로 이동합니다. 스택은 CA가 됩니다...
-
( d, c/e,cccc ) - 스택의 맨 위가 c이고 현재 입력 기호가 d이면 스택에서 4ds를 팝하고 q4로 이동합니다.
-
( $, I/I, I) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q5로 이동합니다. NULL 문자열의 경우.
-
-
상태 q1 −
에 대한 전환-
( c, c/c,c ) - 스택의 맨 위가 c이고 현재 입력 기호도 c인 경우 c를 스택의 맨 위로 푸시하고 q1에 유지합니다. 스택이 cc가 됩니다.... 다음 d까지 cs를 계속 푸시합니다.
-
( d, c/e,cccc ) - 스택의 맨 위가 c이고 현재 입력 기호가 d이면 스택에서 4ds를 팝하고 q2로 이동합니다.
-
-
상태 q2 −
에 대한 전환-
( d, c/e,cccc ) - 스택의 맨 위가 c이고 현재 입력 기호가 d이면 스택에서 4ds를 팝하고 q2로 이동합니다.
-
( b, a/e,aa ) - 스택의 맨 위가 a이고 현재 입력 기호가 b이면 스택에서 2를 팝하고 q3으로 이동합니다.
-
-
상태 q3 −
에 대한 전환-
( b, a/e,aa ) - 스택의 맨 위가 a이고 현재 입력 기호가 b이면 스택에서 2를 꺼내고 q3에 남습니다.
-
( $, I/I, I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q5로 이동합니다. NULL 문자열의 경우.
-
-
상태 q4 −
에 대한 전환-
( d, c/e,cccc ) - 스택의 맨 위가 c이고 현재 입력 기호가 d이면 스택에서 4ds를 꺼내고 q4에 남습니다.
-
( $, I/I, I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 q5로 이동합니다. NULL 문자열의 경우.
-