比奥数更硬核的题目:equivalence of context free grammar (转

e
edison2012
楼主 (未名空间)

【 以下文字转载自 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
heteroclinic

严格说你得先给出元字母表
就是你parser 不会毁棋
悔棋
很多要捏造一个程序语言
往往到处乱插

h
heteroclinic

说说思路
我不是这个领域的
感觉应该是遍历的问题
前序后续或中序

e
edison2012

算了,估计大多数做不出来,还是把答案给出来吧:
http://web.cs.unlv.edu/larmore/Courses/CSC456/F10/Assignments/grmundec.html

【 在 heteroclinic (asymptotically stable) 的大作中提到: 】
: 说说思路
: 我不是这个领域的
: 感觉应该是遍历的问题
: 前序后续或中序