我有以下正则表达式： ((abc)+d)|(ef*g?)
我创建了一个 DFA（我希望它是正确的），你可以在这里看到
任务是创建一个常规语法（乔姆斯基层次结构类型 3），但我不明白。但我创建了一个常规语法，如下所示：
S → aT
T → b
T → c
T → dS
S → eT
S → eS
T → ε
T → f
T → fS
T → gS
最好的问候帕特里克
问问题
136 次
1 回答
0
类型 3 Chomsky 是限制使用以下规则的常规语法类：
X -> aY
X -> a,
其中 X 是任意非终结符和任意终结符。该规则仅在右侧不存在A -> eps时才被允许。A
建造
我们注意到正则表达式包含两种可能性，要么 (abc)+d 要么 ef*g?，因此我们的第一条规则将是S -> aTand S -> eP。这些规则允许我们开始创建两种可能性之一。请注意，非终结符必然不同，它们是相应自动机中完全不同的分离路径。接下来我们分别继续使用这两个正则表达式：
(abc)+ 我们至少有一个序列 abc 后跟 0 次或多次出现，不难看出我们可以这样建模：
S -> aT
T -> bU
U -> cV
V -> aT # repeat pattern
V -> d # finish word
e*g? 这里我们有一个 e 后跟零个或多个 f 字符和一个可选的 g，因为我们已经有了第一个字符（前两个规则之一给了我们），我们继续这样：
S -> eP
S -> e # from the starting state we can simply add an 'e' and be done with it,
# this is an accepted word!
P -> fP # keep adding f chars to the word
P -> f # add f and stop, if optional g doesn't occur
P -> g # stop and add a 'g'
结论
将它们放在一起，它们将形成该语言的语法。我试图写下思路，以便您理解。
作为练习，试试这个正则表达式： (a+b*)?bc(a|b|c)*
于 2015-01-14T18:01:04.787 回答