NPDA는

Question

는

는 말의 우리가 그 언어 L.를 받아들이는 NPDA의 두 가지 상태로 전환 그래프를 그리고하자하고 싶은 말은하자가이 NPDA 것 정확히 2 개의 주를가집니다. 이것에 대한 내 생각은 첫 번째 주에서 모든 것을 다한 다음 두 번째 주를 큰 피날레로 사용하는 것입니다. 그래서 같이 :

하지만 람다 전환이 q1가 발생합니다 모르겠어요 또는 가능성이 난에 노력하고 있기 때문에 더 나은 방법이있다이 할 수있는 더 좋은 방법이 존재하는 경우, 이것을 나에게 가르쳐 라. 아마도 누군가가 나를 여기로 돌아올 수 있을까요?

Answer 1

거의 다 알았습니다. 현재 NPDA가 "acb"를 수락하기 때문에 n>=1 요구 사항을 놓쳤습니다. 스택 심볼 5는 어쨌든 사용되지 않으므로 (b, 4)/5는 필요하지 않습니다.

따라서 "c"앞에 "b"가 있는지 여부를 나타 내기 위해 1과 2 사이의 다른 스택 기호가 필요합니다.

 
q0-q0   q0-q1 
(a,Z)/1Z  (b,3)/λ 
(b,1)/2  (b,4)/λ 
(b,2)/2  (b,5)/λ 
(c,2)/3 
(b,3)/4 
(b,4)/5