automata - 正则表达式澄清的有限自动机

Question

你能检查一下吗：https ://dl.dropbox.com/u/25439537/finite%20automata.png

这是一个检查作业，所以不要担心。我只是想澄清一下我的答案是否正确，因为它被我的老师标记为不正确。

我的答案是 ((a+b)(a+b))*a 第一个 (a+b) 表示上箭头。第二个 (a+b) 表示下箭头。最后一个'a'告诉我们它应该总是以'a'结尾。

我只是想记录很多专家的证据，以便我可以把它交给我的老师。

Answer 1

我相信你的回答是正确的。

让我们将整个过程分为两个部分：（1）从 开始start，然后返回start；(2) 去start接受end。显然，（1）部分是一个循环。

对于 (1)，从 开始start，接受b或a。因为b，该b(a+b)回去了。因为a，该a(a+b)回去了。所以 (1) 是b(a+b) + a(a+b)是(a+b)(a+b)。

对于 (2)，它是a'.

所以，最终的结果是(loop in (1))* (2)ie ( (a+b)(a+b) )* a。

按照上面的描述，你也可以拿出两者等价的证明。证明部分（a）自动机接受的每个序列都在集合中((a+b)(a+b))*a；部分 (b) 集合中的每个序列((a+b)(a+b))*a都被自动机接受。

Answer 2

您的答案是错误的，因为它不提供以b开头的字符串。

路径(start) -> b -> a+b -> a -> (end)被您的有限自动机接受，但不被您的正则表达式接受。您的答案正确的最简单的反例是正则表达式拒绝字符串“baba”。

顺便说一句，如果老师给你的正则表达式没有两个同心圆的“结束”状态（表示接受状态），那可能是一个棘手的问题。没有接受状态意味着你的自动机拒绝一切。最好的描述方式就是写下 {}（空集）。