L ={0m1(n+m)2n | m,n =0} C++

언어 "L"이 주어지고 작업은 1의 발생이 0과 2의 발생을 더한 것임을 설명하는 주어진 언어에 대한 푸시다운 오토마타를 구성하는 것입니다. 또한 0과 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에서 허용되는 문자열은 -

• 0 ^분 1 ^분 − 01, 0011, 000111 등. 0의 수는 아니오와 같습니다. 1초. n이 0이면 2가 없습니다. 0을 계속 누르고 첫 번째 1이 발생하자마자 0을 팝니다. 문자열 끝에 도달했는데 0이 없으면 문자열이 허용됩니다.

• 1 ⁿ 2 ⁿ − 12, 1122, 111222 등. 1의 수는 아니오와 같습니다. 2초의. m이 0이면 0이 없습니다. 1을 계속 누르고 처음 2가 발생하자마자 1을 팝니다. 문자열 끝에 도달하고 1이 없으면 문자열이 허용됩니다.

• 0 ⁿ 1 ^m+n 2 ^분 − 0112, 001112, 001112 등. 1의 개수는 개수의 합과 같습니다. 0과 2의. 첫 번째 1이 발생하는 즉시 0을 계속 누르고 0이 남지 않을 때까지 0을 팝합니다. 이제 처음 2가 나타날 때까지 다시 1을 누릅니다. 그런 다음 각 2에 대해 1이 없을 때까지 1을 터뜨리기 시작합니다. 끝에 도달하고 1이 남지 않으면 문자열이 허용됩니다.

• NULL 문자열도 허용됩니다. 0 ⁰ 1 ⁰ 2 ⁰

기계를 이해하자

• 상태 q0 −

  에 대한 전환

  • ( 0, I/0I ) - 스택의 맨 위가 I이고 현재 입력 기호가 0이면 스택의 맨 위로 0을 누르고 q0에 유지합니다. 스택이 0I가 됩니다...

  • ( 0, 0/00 ) - 스택의 맨 위가 0이고 현재 입력 기호도 0이면 0을 스택의 맨 위로 푸시하고 q0에 유지합니다. 스택이 00이 됩니다.... 다음 1 또는 2가 될 때까지 0을 계속 누릅니다.

  • ( 1, I/1I ) - 스택의 맨 위가 I이고 현재 입력 심볼이 1이면 스택의 맨 위로 1을 누르고 q1로 이동합니다. 스택은 1I가 됩니다...

  • ( 1, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 0을 팝하고 q1로 이동합니다.

  • ( 1, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 0을 팝하고 q1로 이동합니다.

• 상태 q1 −

  에 대한 전환

  • ( 1, 1/11 ) - 스택의 맨 위가 1이고 현재 입력 기호도 1이면 스택 맨 위로 1을 누르고 q1에 유지합니다. 스택은 11이 됩니다.... 다음 0 또는 2가 될 때까지 1을 계속 누릅니다.

  • ( 1, 0/$ ) - 스택의 맨 위가 0이고 현재 입력 기호가 1이면 0을 팝하고 q1에 남습니다.

  • ( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 qf로 이동합니다.

  • ( 2, 1/$ ) - 스택의 맨 위가 1이고 현재 입력 심볼이 2이면 1을 팝하고 q2로 이동합니다.

• 상태 q2 −

  에 대한 전환

  • ( 2, 1/$ ) - 스택의 맨 위가 1이고 현재 입력 기호가 2이면 1을 팝하고 q2에 남습니다.

  • ( $, I/I ) - 스택의 맨 위가 I이고 입력이 없으면 아무 것도 하지 않고 qf로 이동합니다.