문맥 자유 문법 변환

Question

Chomsky normal form을 Backus–Naur Form으로 또는 그 반대로 변환 할 수있는 소프트웨어가 있다면 알려 주시기 바랍니다.

Answer 1

BNF가 이미 CNF에 있다는 원래의 대답은 잘못되었습니다. here (PDF)에 설명 된대로 컨텍스트없는 문법을 CNF로 변환 할 수 있습니다. 변환 과정은 Sipser 두 번째에 나와 있습니다. 106-109 페이지에 액세스 할 수 있습니다. 이 프로세스를 자동화하는 기존 소프트웨어가 있는지는 알 수 없습니다 (단, 쓰기 쉽다).

Answer 2

글쎄, 촘스키 노멀 양식과 배 커스 - 나 우어 양식은 실제로 같은 종류의 개념이 아니기 때문에 그렇게 생각하지 않습니다. 그러나 당신이 우리에게 도움이 될 수 있도록이 소프트웨어가 필요한 것을 말하면됩니다.

이제부터 물어 보니, Chomsky Normal Form에 BNF 문법을 정규화하는 코드가 필요하다고 가정합니다. 내가 아는 한, 그러한 소프트웨어는 존재하지 않지만 실제로는 계산 상 가능하다고 가정 할 때 일부 존재할 수 있습니다.

그러나 실제로 필요한 것이 무엇인지 구체적으로 설명하면 해당 작업에 대한 유용한 조언을 드릴 수 있습니다.

편집 : 내 책에서 조금 파기 한 후, 임의의 CFG를 Chomsky Normal Form으로 변환하는 알고리즘을 공식화하는 것이 가능하다는 것이 밝혀졌습니다. 나는 실제 알고리즘이나 그 복잡성을 가지고 있지 않다.

Answer 3

JFLAP 당신이 찾고있는 것을 할 수 있습니다.

저는 아직 사용하지 않았지만 오토마타 교수가 추천 한 제품입니다.

"JFLAP이란 무엇인가?" 페이지에서 "CFG -> CNF"로 변환 할 수있는 것처럼 보입니다.