0
언어를 허용하는 푸시 다운 오토 마트를 작성하는 방법은 무엇입니까?
누군가이 언어에 대해 푸시 다운 오토 마톤을 만드는 방법을 설명해주십시오. 당신이 그걸 잘 설명 할 수 있다면, 언어의 표기법을 이해할 수 없습니다. 고마워요
A
답변
1
표기법이란 다음과 같습니다 : n 자 a와 그 뒤에 m 자 b로 시작하는 모든 단어로 구성된 언어. 또한, n과 m의 수는 동일하지 않아야한다.
PDA로 이것을 받아들이는 명백한 방법은 다음과 같습니다. 처음부터 모든 것을 읽을 때마다 스택에 하나씩 넣습니다. 당신이 b를보기 시작할 때, 당신이 읽는 모든 것에 대해 스택 중 하나를 제거합니다. 마지막 b가 마지막 스택 심볼을 제거하면 n = m이고 PDA는 거부해야합니다. 그렇지 않으면 단어가 b 인 경우 받아 들여야합니다.
+0
다이어그램에서 입출력이 올바른지 확인하십시오. –
상황은 PDA 정의의 세부 사항, 특히 수용 조건에 조금 의존합니다. q0에서 q1 로의 전환은 푸시가 아닌 팝해야합니다. 나는 모든 엡실론 전환점이 무엇인지 확실하지 않다. 수락 상태가 필요하거나 빈 스택으로 수락합니까? 더 이상 움직일 수 없습니까? 아마도 빈 스택을 테스트 할 수 없습니다. 처음 단계에서 당신은 "ac"를 누를 수 있고 나중에 스택에서 c를 읽을 때 당신은 당신이 바닥에 도달했다는 것을 알게됩니다. –