标签: finite-automata

问题：构建一个仅接受不以 ba 结尾的单词的 FA。我想为这个问题画DFA，但我不明白我该怎么做，请帮我画这个

我正在攻读离散数学考试,我发现这个练习是我无法弄清楚的.

"为字母表中的语言Sigma = {0,1,2}建立一个基本的有限自动机(DFA,NFA,NFA-lambda),其中字符串中元素的总和是和,这个总和大于3"

我曾尝试使用Kleene的Theorem连接两种语言,例如连接与此正则表达式相关联的语言:

(00 U 11 U 22 U 02 U 20)* - 偶数元素

用这个

(22 U 1111 U 222 U 2222)* - 总和大于3的那些

这有意义吗？？我觉得我的正则表达式很松弛.

我将从两个更简单的DFA的交集构建DFA.第一个更简单的DFA识别至少有三个0的所有字符串的语言,第二个更简单的语言DFA识别最多两个1的字符串语言.字母表是(0,1).我不确定如何构建一个更大的DFA结合两者.谢谢!

我需要使用McNaughton-Yamada算法为CS类构建DFA.问题是算法是补充材料,我不清楚它究竟是什么.这是一种在给定RegEx的情况下查找DFA还是找到DFA并将其最小化的方法？我似乎无法找到有关该主题的任何信息.

我很困惑,因为我们的教师在课堂上发现DFA后所显示的最小化程序似乎与我们书中描述的"标记"最小化没有任何不同.

感谢您的回复,

弥敦道

我们都知道这(a + b)*是一种仅含有符号a和符号的常用语言b.但是(a + b)*是一个无限长度的字符串,它是规则的,因为我们可以建立一个有限的自动机,所以它应该是有限的.

有人可以解释一下吗？

我实施了一个levenshtein trie来找到与给定单词相似的单词.我的目标是快速进行拼写纠正.

但是我发现有更快的方法可以做到这一点:

Levenshtein Automata

我只是有一个问题...我不明白这里写的是什么 .有人可以用简单的词语向我解释levenshtein自动机的想法和基本功能吗？

我有一个快速的问题。这里的上标加号是什么意思？

= {w ? {0,1} : w ? (0^+)(1^+)}

自从我完成这些以来已经有一段时间了。这是用于制作非确定性有限自动机

常规语言在串联下是封闭的 - 这可以通过将一种语言的接受状态与 epsilon 转换为下一种语言的开始状态来证明。

如果我们考虑语言 L = {a^n | n >=0}，这种语言是正则的（它只是一个*）。如果我们将它与另一种语言连接起来 L = {b^n | n >=0}，这也是正则，我们最终得到a^nb^n，但我们显然知道这不是正则。

我的逻辑哪里出了问题？

我想构建一个接受以下语言的确定性有限自动机:

{w∈{a,b}*:w中的每个a前面都有ab}

到目前为止,我已经>⨀--- b ---> O --- a ---> O.

'>'=初始状态

⨀=最终状态

我有一些关于状态消除和术语的问题。

在上面的示例中，DFA 处于接受状态，必须以符号 0 开始并以 1 结束。

如果我将其转换为正则表达式，则上部将是

底部将是

这是我的问题，我不知道如何将顶部和底部部分添加到单个表达式中。我也不完全确定如何进一步消除 q2 符号 1 。

会是 0(0*(0+1))1* 吗？

感谢任何可以提供帮助的人！