问题标签 [automata-theory]

你知道任何实现图灵机和有限状态自动机等抽象机器的编程语言吗？

也就是说，处理以下输入：

• 一个 5 元组（来自形式语言 101 的臭名昭著的 ⟨Q,Σ,δ,q0,F⟩），一个用于图灵机的7 元组或抽象机器的任何其他形式表示。
• 一个输入词。

并告诉我输入的词是否是接受词。

谢谢，

亚当

我创建了一种特殊用途的“编程语言”，故意（通过设计）不能两次评估同一段代码（即它不能循环）。它本质上是用来描述一个类似流程图的过程，其中流程图中的每个元素都是一个条件，它对同一组数据执行不同的测试（不能修改它）。分支可以拆分和合并，但不能以循环方式，即。流程图不能循环回到自身。当到达分支结束时，返回当前状态并退出程序。

写下来时，典型的程序在表面上类似于纯函数式语言的程序，除了不允许任何形式的递归并且函数永远不能返回任何内容。退出函数的唯一方法是调用另一个函数，或者调用返回当前状态的通用退出语句。通过采用结构化编程语言并删除所有循环语句，或者通过采用“非结构化”编程语言并禁止在代码中倒退的任何 goto 或 jmp 语句，也可以实现类似的效果。

现在我的问题是：有没有一种简洁准确的方式来描述这种语言？我没有任何正式的CS背景，对于自动机理论和形式语言理论的文章我很难看懂，所以我有点不知所措。我知道我的语言不是图灵完备的，经过巨大的痛苦，我设法向自己保证，我的语言可能可以归类为“常规语言”（即可以由只读图灵机评估的语言），但有更具体的术语吗？

如果该术语对于精通一般编程概念但没有正式 CS 背景的观众可以直观地理解，则可以加分。如果有一种特定类型的机器或自动机可以评估这种语言，也可以加分。哦，是的，请记住，我们不是在评估数据流 - 每个元素都可以（只读）访问完整的输入数据集。:)

我正在阅读一本关于自动机理论的书，书中给出了一个示例，即具有相同数量的 0 和 1 的语言与 1*0* 相交会导致 1n0n，其中 n > 0

所以我的问题是，我怎样才能找到一些与 1*0* 相交时也会产生 1n0n 的常规语言。有没有办法考虑这个？

更新：感谢您的回答！我想我想要找到的是一些常规语言，所以像 1n0n 这样的语言是行不通的；）有可能吗？有任何想法吗？

我正在研究一些测试准备材料并坚持这个问题。

显示 L = {we {a,b}*: w = wR 且每个 a 都紧跟 ab} 的上下文无关文法。

wR 是相反的 w。所以，在英语中，每个“a”后面跟着一个“b”的回文，使用任意数量的a和b。

到目前为止，我得到了这个反向部分，但我不知道如何合并每个 a 后跟 ab 部分，同时确保回文属性仍然有效。

任何帮助是极大的赞赏！

不太确定这是否是正确的论坛，但在理论计算机科学上建议我将它移到这里......

有限状态机的典型字母大小是多少？

我目前正忙于实现一个高性能的 FA 库，在继续之前需要做一些设计考虑。我的状态空间将按 2 147 483 647 ( Integer.MAX_VALUE) 的顺序排列，我觉得这已经绰绰有余，即使对于非一般用途也是如此。现在，剩下的就是字母空间。

假设字母表通常只由所有可显示的字符组成（在这种情况下，它可以存储为 abyte会带来非常好的性能），这有什么好处吗？还是应该将字母符号翻译成Strings，以便您拥有字母标签？在这种情况下，我需要保留一个将 aString转换为 a或的 Map int，具体取决于我想要制作的大小。shortbyte

如果您不熟悉 LTL（线性时序逻辑），请跳过此问题！是的，LTL 对编程非常重要，因为它是我们用来验证程序的模型检查系统的核心。

鉴于这些命题符号及其含义...
Gp - 总是 P
Fp - 有时 P

以下陈述是什么意思？

我很难理解围绕 LTL 的逻辑，并且无法理解上述陈述，感谢您的帮助！

I am studying LBA (linear bounded automata). Trying to figure it out how to solve some exersise.

So I wonder if there is an easy way to make a LBA given a Context-sensitive grammar.

This is thinking like how you can go from LR grammar to DFA (deterministic finite automata).

thanks in advance

您如何确定特定字母表上有多少不同的转换图？例如，字母表 {x, y} 上有多少个 TG。我正在上一堂课，上面有 Daniel IA Cohen 的书“计算机理论导论”中的类似问题。有很多关于如何创建 TG 的示例，但无法确定每种语言可以创建多少个。我假设我正在寻找有限数量的 TG？非常感谢！

我正在为自动机理论课做作业。到目前为止，它只是涉及正则表达式的证明，并没有太疯狂。无论如何，我的问题是什么是连接的正确集合符号？例如，我知道 R + S 将与 R union S 相同，但对于我的一生，我不记得等效于串联的集合论是什么。

我不会发布任何问题，因为我认为我会很好地解决它们，有人可以在正确的方向上给我一点帮助吗？

PDA接受哪些类型的语言，其中堆栈大小限制为 20 个项目？

在我看来，它仍然应该是CFL，因为有一个临时内存要存储。