问题标签 [automata-theory]

It was written in ullmans book but i did not under stand well how it works. Can anybody explain even in simple context? I'd be really glad.

在考虑自动机时，它们通常被认为是有限字母表。以下是两种类型的自动机，它们可以处理无限字母表上的单词（为清楚起见，包括定义）。

分别附加在单词开头和结尾的符号 [ 和 ] 是分隔符，不在字母表中。也就是说，自动机处理形式为w = [ v ] 的单词，其中v是字母表的一个元素。

字母表上的k 寄存器自动机A 是一个 5 元组 (Q, q_0, F, t_0, P)，其中：

• Q 是一组有限状态；

• Q 中的 q_0 是初始（或开始）状态；

• F（Q 的子集）是最终（或接受）状态的集合；

• t_0 : {0,1,...,k}--> 字母联合 {[,]} 是初始寄存器分配；和，

• P 是形式为 (i, q)-->(q', d) 或 q-->(q', i, d) 的有限转换集，其中 i 在 {0,1,...,k }, q, q' 在 Q 和 d 在 {Stay, Left, Right}。

符号有限自动机 (SFA) M 是一个 5 元组 ( A , Q, q_0, F, d)，其中：

• A 是一个有效的布尔代数（字母表）；
• Q 是一组有限状态；
• Q 中的 q_0 是初始（或开始）状态；
• F（Q 的子集）是最终（或接受）状态的集合；和，
• d（Q x Y_A x Q 的子集）是有限的转换集。

研究表明，对于寄存器自动机，等价是不可判定的，但在符号自动机中，等价是可判定的。我的问题是为什么？这两种自动机类型的工作结果相似，那么为什么我们不能将一种归约到另一种呢？

有人告诉我这是一个非常简单的问题，但我似乎无法在任何地方找到答案，所以感谢您的帮助！:)

我目前的想法是，SFA 要求他们的字母表是有效的布尔代数，而 RA 可以处理任何事情，因此他们的字母表不必遵循布尔代数的规则。我不知道如何正确地将这个想法转化为任何有用的东西。

给出生成以下语言的上下文无关文法。在所有部分中，字母 ∑ 是 {x,s}。{w| w 以不同的符号开始和结束}

我需要有关正则表达式的帮助。我想要一个正则表达式，其中字母 b 永远不会增加三倍。这意味着其中没有任何单词包含子字符串 bbb。语言只包含字母 {a,b}

在介绍计算理论书籍时，对于该语言 ，状态图如下：

我知道可能有其他图表，但我怀疑我找到的解决方案可能是错误的，这与原始图表略有不同：

对于我的解决方案，我将不胜感激任何计数器输入。

标题说明了一切。我需要一些想法。nfa 输入看起来像这样，并且没有 epsilon 移动。

等等，这意味着 1 和 2 是最终状态，而使用“a”我可以从状态 0 到状态 2。

我用

保存数据，其中 v[i] 是包含从状态 i 出发的所有路径的向量。 当有多个状态时，我需要一个关于如何命名新状态的想法

因为我无法创建状态 123 或类似的东西。 我如何检查一个多重集是否已经转换为一个状态？

有人可以向我解释如何为这种语言创建下推自动机。如果您能解释一下，我不明白该语言的集合符号也很好。谢谢

我有以下语言及其正则表达式

{w ∈ {a, b}* : w 以 bab 为前缀，以 babaa 为后缀}

回答：

正则表达式 = bab(a ∪ b)*babaa ∪ babaa ∪ bababaa

为什么需要加粗部分？

我有一个自动机理论项目，我想将算法转换为编程语言（不管用什么编程语言来解决这个问题）

嗯，我有这些命令

我们输入一个字符串，然后将其转换为 char 以便我们进行比较，

例如我们输入了这个输入

01001

为了清楚起见，我将添加更多输入以了解我的意思，

01000001

{有效输入}

{错误输入}

0

{错误输入}

我们将检查第一个数字是否为0，如果是，我们将此字符串复制到另一个数组1，然后将其转换为1，如果相同则将其复制到数组2，然后在这里我们需要使用for或进入一个循环foreach，我们想检查下一个值是否为 0（没有最后一个字符），所以我使用 a.length-1 来确保它不会使用最后一个，当我们看到新值 1 时，我们移动到最后一个数组，必须为 1。我们将使用 Console.WriteLine(""); 程序遵循顺序

我做了类似的东西（在 C# 中）：

如何制作新数组并复制并使用它来签出

根据 Sipser 的《计算理论导论》：如果 A 是机器 M 接受的所有字符串的集合，我们说 A 是机器 M 的语言，写成 L(M) = A。我们说 M 识别 A ...一台机器可以接受多个字符串，但它总是只能识别一种语言。并且我们说如果 A = {w| 则 M 识别语言 A M 接受 w}。

我想这个问题已经得到了回答，但我想知道是否有人对此有任何想法，如果我们可以说关于常规语言的子集有什么有趣的事情，是否可以说原始 DFA 识别它们并且原始 DFA 和识别较小语言的 DFA 之间是否存在任何有趣的关系