계획 :^IB^2I

Question

내 시험 오토마타 및 형식 언어에 대한 공부

, 나는 언어를 인식하는 PDA 설계 할 수 있습니다

을^IB^2I되도록 I> = I는 솔루션이있을 것이라고 생각

1

각각 "A"I는 "B"를 얻는 경우 나, 두 개의 X 스택 테이프로부터 판독에 테이프와 나는 스택 맨 위에 X가있다. 빈 테이프를 읽으면 마침내 하나의 X가 튀어 나오고, 나는 Zo (스택 마커 하단), 문자열이 허용됩니다. 내 질문은 : 하나의 계산 단계에서 두 개의 연속적인 X를 쌓을 수 있습니까?

Answer 1

한 번에 두 개의 X를 누르고 X를 한 번만 누른 다음 테이프에서 아무것도 소비하지 않고 다른 X를 밀어 넣는 상태로 전환 할 필요가 없습니다. 전환 함수는 ΣUNION {ε}이므로 입력을 소비하지 않고 스택을 혼란시킬 수 있음을 기억하십시오.

짧은 대답 : 스택에 N 가지를 원하십니까? N 개의 상태로 만듭니다. 그냥 사전에 N 알려져 있는지 확인하십시오 :)

Answer 2

하나의 계산 단계에서 두 개의 연속적인 X를 쌓을 수 있습니까?

"푸시 다운 오토 마톤"을 정의하는 방법과 구체적으로 어떻게 전환 기능을 정의하는지에 따라 다릅니다. 한 번에 전체 문자열을 푸시 할 수 있도록 PDA를 정의 할 수 있습니다. 당신은 당신의 코스 텍스트를 확인하거나 교수님과 그 종류의 것이 코스에서 허용 될 것인지를 확인해야합니다.