问题标签 [formal-languages]

我正在尝试为带有字母 a、b、c 的语言编写正则表达式查询，以使 a 永远不会与 b 相邻。

是否可以仅使用交替（加）、连接和重复（乘）运算符来完成？

L = w 属于 {a,b,c}* 使得 a 永远不会与 b 相邻

我正在自学正式语言（Aho's，Hopcroft），但我很难使用正则表达式。

我已经能够处理简单的任务，但这一项已经构成了挑战，至少对我来说是这样。如果你不能算到现在怎么解决这个问题，我不习惯这种类型的计算。
一定有一些属性或东西可以让我概括答案，我可以把它作为一个常规表达式。

到目前为止，我已经设计出至少有 2 到 3 种情况：

• 如果 sum=3k，则求和 mod3=0
• 如果 sum=3k+1，则求和 mod3=1
• 如果 sum=3k+2，则求和 mod3=2。

但是我已经意识到，可能有很多组合会发生求和，所以找不到正则表达式必须遵循的模式。

ex的字符串。（大括号是为了便于阅读）如果总和是字符串中的“10”，则{122211}0末尾有零。情况可能是这样的，所以必须在最后，依此类推。{sum=3k}0{1222111}1{sum=3k+1}

这可能是解决问题的正确途径，也可能不是解决问题的正确方法，但我愿意接受任何建议，非常感谢任何帮助。

我知道将正则表达式转换为 NFA，有一个算法。

但我想知道是否有一种算法可以将 NFA 转换为正则表达式。如果有，它是什么？

如果没有，我也想知道是否所有 NFA 都可以转换为正则表达式。是否存在无法表示正则表达式的 NFA？

谢谢！:D

为一堂课做作业，我想到了这个问题：

对于以下每个正则表达式，请给出不在表达式定义的语言中的最小长度字符串。

1. (bb)*(aa)*b*
2. a*(bab)*∪b∪ab

我将尝试只在第一个上获得帮助，看看我是否能弄清楚第二个。这是我所知道的：Kleene * 表示 0 个或多个可能的元素。集合的并集是包含集合 a 和集合 b 的所有元素而不重复元素的集合。从插入 lambda 开始解决第一个问题，我得到：

第一次运行：bbaab
第二次：bbbbaabaabbaabbbbaab
第三次：bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

如果我做得正确，那么长度为 0 到 5 的字符串不在该语言中。我这样做正确吗？

L1 = { a^ib^j | 我,j>=0 }

我的尝试：

我无法确认我的答案，这是正确的吗？

这是维基百科中可判定的定义

在可计算性理论中，一个不可判定的问题由一系列需要特定是/否答案的实例组成，因此没有计算机程序可以在给定任何问题实例作为输入的情况下终止并在有限数量后输出所需的答案的步骤。更正式地说，不可判定问题是语言不是递归集的问题

递归集是递归可枚举集的子集。有一些递归可枚举的语言在递归集合之外。那么为什么递归可枚举语言不是不可判定的呢？

我想编写一个词法分析器生成器来将 MATLAB 语言的基本子集转换为 C#、C++ 等。为了帮助我做到这一点，我想找到一个包含 MATLAB 形式语法的文档。花了一些时间对此进行了调查，似乎 Mathworks 没有提供。

有谁知道我在哪里可以找到这样的文件？

我如何证明这种语言是否正常？

L = {a ⁿ b ⁿ : n≥1} 并集 {a ⁿ b ⁿ⁺² : n≥1}

我正在寻找处理一般描述形式语言（字符串集）而不仅仅是语法层次结构的数学理论。

我如何为这个问题绘制 NFA（自动机）？

首先它应该接受：

• 字母 = x,y,z

• L= { w | w 使得出现次数 x,y,z 之一是三的倍数。}

例如：{xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}