我需要帮助为下面的语言构建左线性和右线性语法？
a) (0+1)*00(0+1)*
b) 0*(1(0+1))*
c) (((01+10)*11)*00)*
对于a)我有以下内容:
Left-linear
S --> B00 | S11
B --> B0|B1|011
Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1
它是否正确？我需要帮助b&c.
grammar computation-theory regular-language formal-languages
我被要求显示DFA图和RegEx作为RegEx的补充(00 + 1)*.在之前的问题中,我必须证明DFA的补充是封闭的并且也是正则表达式,所以我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受国家.
但是,似乎RegEx的初始接受状态是{00, 1, ^},最终接受状态也是{00, 1, ^}如此.因此,交换它们只会产生完全相同的RegEx和DFA,这似乎是相互矛盾的.
我做错了什么,或者这个RegEx应该没有真正的补充？
谢谢
?: Q × ? ? Q用英语怎么说？描述什么×和?意思也会有所帮助.
在我的计算理论课中,我们有一个证明语言是常规的任务.该语言定义为:
B = { | 在与含有至少 1秒,对}
1kyy{0, 1}*ykk >= 1
这种语言在我看来就像需要一个下推自动机来为此创建一台机器,但是如果有人能够推动我朝着正确的方向努力来证明这是一种常规语言.向我展示其中一种证明方法:创建NFA,DFA,正则表达式或常规语法会很有帮助.