0
컴퓨터 과학 이론에 대한 연구에서 어떤 문제가 있습니다 ...2 주에 cfg을 (를) PDG로 변환하는 방법?
컨텍스트없는 문법 (cfg)을 해당 푸시 다운 오토 마톤 (pda)으로 변환 할 수있는 알고리즘을 설명 할 수 있습니까?) 상태가 2 개일뿐입니다.
A
답변
0
상태 1 : 허용하지 않습니다. 자기 자신으로의 빈 전환으로 빈 스택으로 S를 누르십시오. G에서 각 프로덕션에 대한 자체 전환을 비우지 만 생성 된 문자열을 스택으로 밀어 넣습니다. 스택 맨 위에 x가있는 터미널 심볼 x를 읽을 때 자기 자신을 비운다. 빈 스택에서 상태 2로 비어 있습니다.
상태 2 : 입력 및 빈 스택을 더 이상 허용하지 않습니다.
이론 : 문법 언어로 문자열을 유도하기 위해 스택은 파생물을 작성한 후을 입력 한 다음 입력을 읽을 때이를 팝핑합니다. 입력이 부족하여 스택이 비어 있으면 상태 2로 이동하여 승인 할 수 있습니다.
이 질문은 [cs.se]에 대한 지시 사항보다 훨씬 효과적 일 수 있지만 중복으로 거기에서 닫힐 수 있습니다. 예를 들어 https://cs.stackexchange.com/questions/19946/how-to-get-2-state-pda-for-cfg 또는 다음 검색을 참조하십시오. https://cs.stackexchange.com/search?q= + CFG +를 + PDA로 변환 – rici
이전에 발견했지만 분명히 대답하지 못했습니다. @ rici –