我的常规语法 Regex/DFA

Question

我有以下正则表达式：((abc)+d)|(ef*g?)

我已经创建了一个 DFA（我希望它是正确的），你可以在这里看到

http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid=f4a1d32722d755bdacf04614424330d2

任务是创建常规语法（乔姆斯基层次结构类型 3），但我不明白。但是我创建了一个常规语法，看起来像这样：

S → aT

T → b

T → c

T → dS

S → eT

S → eS

T → ε

T → f

T → fS

T → gS

最好的问候帕特里克

Answer 1

乔姆斯基类型 3 是 class 常规文法，限制使用以下规则：

X -> aY
X -> a,

其中 X 是任意非终结符和任意终结符。规则 A -> eps 仅当 A 不存在于任何右侧时才被允许。

施工

我们注意到正则表达式由两种可能性组成，要么是 (abc)+d 要么是 ef*g?，因此我们的第一个规则将是 S -> aT 和 S -> eP。这些规则允许我们开始创建两种可能性之一。请注意，非终结符必然不同，它们是相应自动机中完全不同的析取路径。接下来我们继续分别使用两个正则表达式：

(abc)+ 我们至少有一个序列 abc 后跟 0 次或多次出现，不难看出我们可以这样建模：

S -> aT
T -> bU
U -> cV
V -> aT   # repeat pattern
V -> d    # finish word

ef*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)*

我的常规语法 Regex/DFA

Regular Grammar to my Regex/DFA

regex

grammar

dfa

chomsky-hierarchy