将正则表达式a * b * + b * a *转换为有限状态自动机

Question

问题是给出在任何B之前出现的所有A或在所有As之前出现的所有B的正则表达式。

我有一个正则表达式为a * b * + b * a *。

我不确定我是否做对了。感谢您的帮助。

Answer 1

如果要使用不确定的有限自动机，可以使用基于正则表达式中的运算进行转换的算法：

• • 变成不确定的分支ε过渡
• 串联变成从状态到状态的顺序转换
• Kleene星变成环状

您的NDA看起来像这样：

        a        b
        ^        ^
q0--e-->q1--e-->q2
 |
 e
 |
 V
q4--e-->q5
v      v
b      a

如果需要确定性有限自动机，可以使用已知算法确定不确定性自动机。否则，我们可以反向运行Myhill-Nerode，以在不可区分关系下找到等价类。这将为我们提供最小DFA的状态。

• e后面可以是L中的任何字符串，并且使用我们的语言；此类为[e]，对应于正在接受的初始状态q0
• a只能跟a b； a是该语言的语言，因此类[a]对应于接受状态q1
• b只能跟在b a之后； b是语言，因此类[b]对应于接受状态q2
• ab只能跟b *; [ab]，第3季度，接受
• ba只能跟a *; [ba]，q4，接受
• aba，bab不是语言，永远无法解决； [aba]，q5，不接受
• 所有其他长度为3的字符串与已经看到的字符串没有区别；我们完成了

因此，有一个DFA具有6个状态-1个初始（q0），5个接受和1个失效（q5）-接受该语言。您可以按以下方式找出过渡：每个状态都在跟随其等效类的任何字符串之后到达。请注意，死态q5必须具有两个自环作为其过渡。

Answer 2

用您自己的语言描述接受哪些字符串，然后在输入a或b之后描述接受哪些字符串。对于每个不同的一组不相同的接受字符串，您将创建一个状态。如果一组接受的字符串包含空字符串，则状态为接受状态。

可接受字符串的集合，输入a之后的可接受字符串和输入b之后的可接受字符串都不同，因此至少需要三个状态。 （a必须紧跟a * b *，b必须紧跟b * a *）。