내 친구가 푸시 다운 오토 마톤에 대해 질문했습니다. 아바 카. 비슷한 문제가 있지만 모든 문제는 0^a 1^a와 같은 짝수를 포함하지만 지금은 3 가지 값을가집니다. 나는 그것에 대해 an example을 찾았지만 내 질문을 변환 할 수 없습니다.푸시 다운 오토 마톤 (a^x b a^y c a^x + y)
aabbabcc:
read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1
top of stack is 0 so push 0
read c pop 0
read c pop 0
어떻게하면 abacaa로 변환 할 수 있습니까?
나는 이것이 잠시 여기에 있었다는 것을 알고 있지만, 누군가 비슷한 질문을하고있는 경우를 대비해 ... 왜 이것을 재촉할까요?
기본적 아이디어는 다음과 같습니다. 푸시 다운 오토 마톤에 스택이 있습니다. 따라서, 매번 스택에 여분의 "a"를 밀어 넣으면서 원하는만큼 많은 것을 읽으십시오. 그런 다음 b를 읽고 다음 상태로 이동하십시오.
이제 모든 것을 다시 스택으로 밀어 원하는만큼 다시 읽으십시오. 그런 다음 c를 읽고 다음 상태로 이동하십시오.
이제 스택 맨 위에서 'a'를보고있는 한 읽어보십시오. 최하위 스택 기호를보고있을 때 최종 승인 상태로 전환하십시오.
더 많은 정보가 있으면 전환이없고 문자열이 허용되지 않습니다 (읽지 않아도되고 아무 것도 떠나지 않아 컴퓨터가 "충돌"합니다). 그렇지 않으면, 이전 상태에서 a를 다 쓴 경우 최종 상태가되지 않고 문자열이 허용되지 않습니다. 처음 두 번 읽은 것만 큼 많이 읽었을 때 더 이상 읽을 입력이 없으면 수락 상태가되고 문자열이 허용됩니다.