PDA에서 사용할 수있는 언어는 무엇입니까?

Question

스택의 항목을 밀고 내릴 때 푸시 다운 오토 마톤의 표기법을 이해하는 데 어려움을 겪고 있습니다.

문자열을 허용하려면 스택이 비어 있어야한다는 것을 알고 있습니다. 내가 전환 다이어그램을 작성하는 경우 입력 0011 내가 이런 식으로 할 것이라고 말에 대한

: 입력이 빈 스택입니다

State   Input   Stack 

q0    0011   ɛ 

q0    011   0 

q0    11   00 

q0    1    100 

q0    ɛ    1100 

때문에 여기

내 PDA입니다 비어 있지 않은가, 이것은 받아 들여지지 않는다?

그래서 내가 그 물건을 잘 넣는다면 ... 나는 이것이 잘못된 것이라고 확신합니다. 왜냐하면 내가 PDA에 어떤 문자열을 넣으면 받아들이지 않을 것이기 때문입니다.

내 실제 질문을 요약하면 첫 번째 비 터미널 (0, ɛ/0) (1, ɛ \ 1) 표기법입니다. 입력 1의 경우, 반대의 경우)?

두 번째 터미널은 의미가 있습니다 ... 글쎄요. 이것은 나를 혼란스럽게합니다. (스택이나 입력에서 문자열을 가져 옵니까?) 스택에서 항목을 제거해야한다고 생각합니까?

그렇다면이 PDA에서 허용하는 언어는 빈 세트입니까? 내가 어디로 잘못 가고 있는지 설명 할 수 없다면?

Answer 1

다른 규칙이 있지만 하나의 공통 규칙은 때 받아 들일 것입니다 :

1. 입력이 소진; 및
2. 귀하는 수락 상태입니다. 및
3. 스택이 비어 있습니다.

실제로 이러한 규칙의 여러 하위 집합을 사용할 수 있으며 다른 규칙 집합을 사용할 수 있으며 컨텍스트가없는 언어에서도 작동하는 시스템을 사용할 수 있습니다. 기계는 그 시스템에서 다른 해석을 가지지 만 표현력은 동일합니다.

위의 3 점 시스템을 가정하면 Welbog이 지적한 것처럼이 PDA는 알파벳 {0, 1} 이상의 짝수 길이의 문장을 허용합니다. 각 주가하는 일에 대해 이야기 해 봅시다.

1. q0 다시 당신이 원하는만큼 반복, 하나 0 또는 1 읽고 스택에 각각 0 또는 1를 푸시합니다. 문자열 x을 읽으면 문자열 x을 스택에 푸시합니다.

2. q1는 스택의 상단에 심볼이있는 경우, 이상, 그것을 떨어져 튀어 이상 당신이 원하는만큼 얻을, 0 또는 1 중 하나를 읽고. 문자열 x을 읽으면 x^R이 스택에서 나옵니다.

우리가 q1 받아들이는 상태를 확인하고 입력이 소진 될 때 스택이 비어있을 것을 요구하는 경우, 그 의미 :

1. x 읽을 경우 우리는 x^R을 튀어 상태 q1에있는 동안 .
2. 상태가 q0 인 경우 x^R을 읽으면 스택에 x^R이 포함됩니다.
3. 우리는 x^R 다음 x을 읽고이를 수락하며, 그래서 우리는 또한, 짝수 길이 회문이 결과이 PDA를 통해 경로가
4. 허용되는
, 즉 짝수 길이 회문는 이후 x^R x 같은 문자열을 받아 PDA는 |x|/2 입력 심볼의 경우 에 남아 있고 q1으로 전환하고 나머지는 |x|/2이라고 읽을 수 있습니다. PDA가 비 결정적이기 때문에 이것은 문자열이 받아 들여진다는 것을 말하는데 충분합니다.