e********2
发帖数: 495 | 1 【 以下文字转载自 Military 讨论区 】
发信人: edison2012 (jimmy), 信区: Military
标 题: 比奥数更硬核的题目：equivalence of context free grammar
发信站: BBS 未名空间站 (Sat Oct 16 15:49:02 2021, 美东)
prove equivalence of context free grammar
比如产生‘a’比‘b’多的字符串，答案给出以下grammar：
S -> TaT
T -> TT | aTb | bTa | a | epsilon
有个学生给出：
S -> B | BA | AB | AS | SA
B -> a | aB
A -> AA | aAb | bAa | epsilon
证明这两个context free grammar （CFG）， 产生相同的language。或证否。 |
h**********c
发帖数: 4120 | 2 严格说你得先给出元字母表
就是你parser 不会毁棋
悔棋
很多要捏造一个程序语言
往往到处乱插 |
h**********c
发帖数: 4120 | 3 说说思路
我不是这个领域的
感觉应该是遍历的问题
前序后续或中序 |
e********2
发帖数: 495 | 4 算了，估计大多数做不出来，还是把答案给出来吧：
简而言之，就是理论上grader无法判断你对不对, undecidability problem
http://web.cs.unlv.edu/larmore/Courses/CSC456/F10/Assignments/grmundec.html
【在 h**********c 的大作中提到】
: 说说思路
: 我不是这个领域的
: 感觉应该是遍历的问题
: 前序后续或中序
|
