1
시작 변수 S가있는 Σ = {0, 1, 2}에 대한 문맥없는 문법 G :
S → 0S0 | 1S1 | 2S2 | Y
Y는 →문맥 자유 문법 (context free grammar)의 경우, 동등한 푸시 다운 오토 마톤으로 변환하려면 어떻게해야합니까?
(22)는 어떻게 동등한 푸시 다운 오토마타
A
답변
2
스택 맨 위에 기호를 밀어 그들을 팝업 수있는 푸시 다운 오토마타로이 설정 않습니다. 최상위 스택 심볼을 기반으로 전환을 기반으로 할 수도 있습니다. 스택을 조작하여 올바른 언어를 허용 할 수있는 메커니즘을 생각해야합니다.
- 그것은 중간
- 에서
22을 가지고 그것은{0, 1, 2}이상 회문은 다음과 같습니다 문법 생성언어는 다음과 같은 특징이 있습니다. 즉, 동일한 전방을 역방향으로 읽습니다.
문자열의 시작 부분을 "기억"해야 문자열의 끝이 거꾸로 반복되는지 여부를 알 수 있습니다. 이것은 스택의 좋은 사용 사례입니다 : 심볼을 볼 때 스택에 심볼을 푸시 한 다음, 심볼을 읽는 동안 심볼을 팝핑 할 수 있습니다. 또 하나의주의 사항 : 우리는 22을 읽은 후에 다시 읽기 시작할 수 있음을 압니다.
첫째, 우리는 모든 것을 읽고 우리가 "22"를 찾을 때까지 스택에 밀어 :
Q s S Q' S'
----------------------
// read 0s and 1s and push them on the stack
q0 0 Z q0 0Z
q0 0 0 q0 00
q0 0 1 q0 01
q0 1 Z q0 1Z
q0 1 0 q0 10
q0 1 1 q0 11
// if you read a 2, pus it on the stack and
// go to a new state where we look for a second 2
q0 2 Z q1 2Z
q0 2 0 q1 20
q0 2 1 q1 21
// if you read a 2 and then 0 or 1, go back to the
// initial state and keep reading input. otherwise,
// if you find a second two, proceed
q1 0 2 q0 02
q1 1 2 q0 12
q1 2 2 q2 22
// assume the '22' we just saw was not the one in
// the middle of the input string and that we need
// to keep reading input.
q2 0 2 q0 02
q2 1 2 q0 12
q2 2 2 q2 22
// assume the '22' we just saw was the one in the
// middle of the input string and that we now need
// to start reading from the stack.
q2 - 2 q3 -
q3 - 2 q4 -
q4 0 0 q4 -
q4 1 1 q4 -
q4 2 2 q4 -
q4 - Z q5 Z
// we read a string in the language and are
// ready to accept in q5. go to dead state q6
// explicitly if still have input.
q5 0 Z q6 Z
q5 1 Z q6 Z
q5 2 Z q6 Z
// consume the rest of the input in the dead state.
q6 0 Z q6 Z
q6 1 Z q6 Z
q6 2 Z q6 Z
전환을 q5과 당신이 문자열을 의미하는 기계를 충돌 정의하면 q6 엄격하게 필요하지 않습니다 명확하게 거부됩니다. PDA가 충돌없이 모든 입력을 정상적으로 처리 할 수 있도록 전환을 포함합니다.
이 PDA는 결정적이지 않습니다. 이 언어에 대한 결정적인 PDA는 없습니다. 기본적으로 22이라는 하위 문자열을 읽은 후에 중간에있는 인스턴스가 22인지 여부를 추측해야합니다. 그렇다면 우리는 회문문이 있는지보기 위해 초기 문자열을 다시 읽어야합니다. 그렇지 않다면 스택에 심볼을 계속 푸시해야합니다.