问题标签 [automata-theory]

在 Σ = {A, B, C} 上定义的所有字符串的语言，它以 B 开头，以 A 结尾，最小长度为 3，并且还为该语言绘制有限自动机。

请用正则表达式的方式和语言图解释一下。在 Σ = {X, Y, Z} 上定义的所有字符串的语言，其中 Y 为第三个字母，Z 为倒数第二个字母

我需要帮助以正则表达式的方式解决。The language of all strings defined over Σ = {X, Y, Z} with Y as the third letter and Z being the second last letter.

我正在尝试设计一个接受语言 L = {w | 的图灵机 a ⁿ b ²ⁿ } 其中 ∑ = {a, b}。

例如机器接受输入：“aabbbb”但不接受“aabb”

我的代码在下面关于该语言；

问题是：这是一台图灵机吗？或者我可以在图灵机中使用堆栈吗？

谢谢

目前我正在学习computation theory，我想出了这个 T - F 问题：

以下语法

产生语言{a^n | n>=1}。

好吧，我不知道我们是否可以这么说，因为这种语法不会停止。它只是创建了一堆，但它不接受任何内容。ε如果我们有一个推导规则，那肯定是。

它与具有以下内容完全相同：

永远不会达到最终状态。

这个语法是 LR(0) 还是 SLR(1)？

我目前正在学习自动机理论课程，但遇到了以下问题。我想出了第一个问题的答案，但对第二个问题的陈述感到困惑。

(i) 给出语言 S* 的递归定义，其中 S = {aa,b}。

第 1 步：Lamba、aa、b 在 S 中。

步骤 2：如果 x 在 S 中，那么 bx 和 xb 也是。

我想确认我的确认我的回答。

以下是我完全困惑的问题，无法想出答案。

(ii) 给出语言 T* 的递归定义，其中 T = {w1, w2, w3, w4} 其中这些 w 是一些特定的词。

我知道找到一个接受给定 NFA 接受的语言的补充的 NFA 的唯一方法是将 NFA 转换为等效的 DFA，然后将非最终状态作为最终状态，将最终状态作为非最终状态。有没有其他方法可以达到同样的效果？

我正在上正式的语言课，即将进行语法测验。我假设会出现这样的事情。

考虑字母表 ∑ = {a, b, c}。构造一个生成语言 L = {bab^nabc^na^p : n ≥ 0, p ≥ 1} 的文法。假设起始变量为 S。

我一直试图证明两个正则表达式是等价的。我知道如果两个正则表达式定义相同的语言，它们是等价的。但是如果不使用 DFA，我就无法证明这一点。

例如，我有问题要证明以下是等价的。

我知道这两种语言都定义了至少有一个“a”和一个“b”的语言。

下面的情况也是如此。

任何帮助将不胜感激。

谢谢

表明正则语言 L 的单词的反义词也是正则的

我对如何处理这个问题感到困惑，我已经被困了几个小时：对于一个单词 x，我们使用 x^r 来表示它的反面。对于语言 L，我们使用 L^r 来表示 {x^r 其中 x 在 L 的集合中}。证明如果 L 是正则的，那么 L^r 也是正则的