푸시 다운 오토 마톤, 2 개 언어 가능 (OR 조건)
숙제에서 우리는 2 개 언어를위한 푸시 다운 오토 마톤을 만들어야했지만, 제 생각에는 이것은 오토 마톤이 둘 다 동일한 두 가지 연습 문제라고 생각합니다.
내가 알기로, 우리는 비 결정적 푸시 다운 오토 마톤을 만들 수 있고, 우리가 문자 a를 읽을 때마다 오토 마톤의 '재량'에 하나의 A 또는 두 번 A를 삽입 할 수 있습니다.
다음으로, 캐릭터 b에 대한 상태가 구축되고, A를 읽을 때마다 스택에서 꺼내게됩니다. 이런 식으로 자동화 장치는 a의 양이 b의 양과 같은 두 언어와 a와 같은 언어가 b의 양의 두 배인 언어를 처리하는 방법을 알고 있습니다.
내가 맞아? 아니면 내가 뭔가를 놓치고 있습니까?
그렇지 않다면 첫 번째 연습에서 "또는"상태를 처리하는 방법을 이해하고 싶습니다.
감사합니다.
답변
이후 $L_2\ne L_3$, 동일한 푸시 다운 자동 장치에 의해 승인 될 수 없습니다. 인식하는 자동 장치를 염두에 두는 것 같습니다.$L_3$. 인식 할 수 있도록 디자인하는 가장 쉬운 방법은$L_2$, 두 개의 결정 론적 푸시 다운 오토마타를 설계하는 것입니다. $\{a^nb^n:n\in\Bbb N\}$ 그리고 하나는 $\{a^{2n}b^n:n\in\Bbb N\}$. 그런 다음 전환이있는 단일 푸시 다운 자동 장치로 결합합니다.$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ 과 $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, 어디 $q_0$ 결합 된 PDA의 초기 상태입니다. $Z$ 초기 스택 기호이고 $q_1$ 과 $q_2$두 보조 푸시 다운 자동 장치의 초기 상태입니다. 즉, 결합 된 PDA가하는 첫 번째 일은 해당 유형의 단어를 찾을 지 여부를 '선택'하는 것입니다.$a^nb^n$ 또는 유형의 단어 $a^{2n}b^n$, 그리고 결정 론적으로 그 선택을 추구합니다.