一个上下文无关语言和正则语言的交集的最短的字符串?
CS theory获得一个答案, 长度可以是exponential的. Shortest string in the intersection of a context-free language and a regular language
实际上有个比上面答案简单多了的答案. F是个free group on 2 elements (say
and
). 而L是所有等于identity的word (这里的alphabet是
) 这个语言的Chomsky范式只有常数大小. R是某一个3n+1个state的DFA. 最短的长度可以有
【一个上下文无关语言和正则语言的交集的最短的字符串?】 具体可以看这个文章的Proposition 5. Automata and Reduced Words in the Free Group
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- 有必要重新开个C店吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉
- 直播会成为品牌传播的另一个途径么有哪些可行的方法感觉有戏又没头绪好捉急。
- 怎样成为一名合格的Python程序员?
- 知乎有没有必要增加一个特别关注功能