0

我正在尝试从有限自动机构造一个正则表达式，但发现我自己完全被这个所困扰。要使用的正则表达式是这样的：

? = 0 或 1
* = 0 或更多
+= 1 或更多
| = 或
_ = 空字符串
@ = 空集
() = 括号

据我了解，字符串必须是以“a*”结尾的“b*”或以“a+bb+”结尾
我现在拥有的是((b*(a+(bb))*)*) ，但这并没有考虑到以“a”结尾的字符串。

如前所述，我 100% 坚持这一点，只是无法理解我应该如何处理这个问题。

图片：http: //img593.imageshack.us/img593/2563/28438387.jpg

代码：
自动机
FA 的类型

州
q1
q2
q3
q4

字母
a
b

初始状态
q3

最终状态
q3
q4

过渡
q1 a q2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

任何解决方案或提示表示赞赏！

4

2 回答 2

2

如果你把它提供给自动机工具（例如，Vcsn），你会得到这个：

In [1]: import vcsn

In [2]: %%automaton a
   ...: $  -> q3
   ...: q1 -> q2 a
   ...: q1 -> q3 b
   ...: q2 -> q2 a
   ...: q2 -> q2 b
   ...: q3 -> q4 a
   ...: q3 -> q3 b
   ...: q4 -> q4 a
   ...: q4 -> q1 b
   ...: q3 -> $
   ...: q4 -> $
   ...: 
mutable_automaton<letterset<char_letters(ab)>, b>

In [3]: a.expression()
Out[3]: (b+aa*bb)*(\e+aa*)

where\e表示空字符串。那么这只是语法转换的问题。

图形化：

Vcsn图形渲染

现场观看这个例子，并玩弄它。

于 2015-05-22T07:38:54.077 回答
0

从 q2 到最终状态是不可能的。删除它，生成的 DFA 应该更容易转换。

据我了解，字符串必须以“a*”结尾的“b*”或以“a+bb+”结尾我现在拥有的是 ((b*(a+(bb)) ) ) 但这不考虑account 一个以'a'结尾的字符串。

想象一下 q3 不是最终状态，而 q4 是初始状态。那么正则表达式会是什么样子呢？将其更改为您想要的应该不会太难，只是不要害怕拥有由正则表达式的多个部分描述的相同状态和/或转换。

另一个提示：我很确定您将需要使用其中一个?或|至少一次。

于 2010-12-20T16:04:56.873 回答