看帖神器
未名空间
追帖动态
头条新闻
每日新帖
最新热帖
新闻存档
热帖存档
文学城
虎扑论坛
未名空间
北美华人网
北美微论坛
看帖神器
登录
← 下载
《看帖神器》官方
iOS App
,体验轻松追帖。
比奥数更硬核的题目:equivalence of context free grammar (转
查看未名空间今日新帖
最新回复:2021年10月17日 0点55分 PT
共 (4) 楼
返回列表
订阅追帖
只看未读
更多选项
阅读全帖
只看图片
只看视频
查看原帖
e
edison2012
2 年多
楼主 (未名空间)
【 以下文字转载自 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
2 年多
2 楼
严格说你得先给出元字母表
就是你parser 不会毁棋
悔棋
很多要捏造一个程序语言
往往到处乱插
h
heteroclinic
2 年多
3 楼
说说思路
我不是这个领域的
感觉应该是遍历的问题
前序后续或中序
e
edison2012
2 年多
4 楼
算了,估计大多数做不出来,还是把答案给出来吧:
http://web.cs.unlv.edu/larmore/Courses/CSC456/F10/Assignments/grmundec.html
【 在 heteroclinic (asymptotically stable) 的大作中提到: 】
: 说说思路
: 我不是这个领域的
: 感觉应该是遍历的问题
: 前序后续或中序
请输入帖子链接
收藏帖子
【 以下文字转载自 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。或证否。
严格说你得先给出元字母表
就是你parser 不会毁棋
悔棋
很多要捏造一个程序语言
往往到处乱插
说说思路
我不是这个领域的
感觉应该是遍历的问题
前序后续或中序
算了,估计大多数做不出来,还是把答案给出来吧:
http://web.cs.unlv.edu/larmore/Courses/CSC456/F10/Assignments/grmundec.html
【 在 heteroclinic (asymptotically stable) 的大作中提到: 】
: 说说思路
: 我不是这个领域的
: 感觉应该是遍历的问题
: 前序后续或中序