问题标签 [automata-theory]

例如，我知道找到模数 n 为 k 的整数很好地映射到有限状态机，并降低自动机在解析确定性语法方面的工作。我想知道是否有类似图灵机的问题。

大家晚上好，我被以下正则表达式卡住了，

我认为表达方式比我的要容易得多，

我必须写下正则表达式和字母表 {a,b} 中接受所有以 b 开头和结尾且 a 为偶数的字符串的 dfa。

我的尝试是进入案件，但结果不是很好：

我试过这样的事情：bb*(阿巴)*(aab)*(aa)*(aab)*(阿巴)*b*b

但我认为这并不完整。

我应该遵循一些一般规则来完成这项任务吗？或者我只需要练习正则表达式？

谢谢，任何提示或帮助将不胜感激。

考虑字母表 V={0, 1, ..., 9} 和语言 L，它由 V 的所有字符串组成，表示所有大于 798 的整数（例如，字符串 799、890、2345、777777 属于到语言 L，而字符串 1、42、711、798 没有）。提供生成语言 L 的所有字符串的正则表达式

我有这个简单的自动机：

然后我写我的系统：

使用 Arden 定理，我可以简化我的表达式：

然后 ：

这似乎是不正确的，但我不明白为什么，有人可以解释我错在哪里吗？

S1：LR = L，当且仅当 L 是回文语言。其中 LR 是通过反转 L 的所有字符串获得的。

S1 是真的吗？

我正在学习上下文无关语法，到目前为止我一直在理解它们，但是这个问题有点让我头晕目眩。

我有以下规则：

我几乎可以肯定他们是不正确的。我知道我会如何只做 i <= j 而不是实际的语言，但是做 j <= 3i 的想法对我来说真的很难掌握，我真的不明白我应该如何在 CFG 中表示它。

我在这里阅读了一些关于设计 CFG 的问题和线索，但它们并没有真正帮助我确定答案的策略。

在此先感谢您的帮助！

DFA 图片：https ://ibb.co/LCW99q9

据我了解，只要包含子字符串“abc”，任何字符串都可以接受；之前的都可以，之后的都可以，包括“λ”。我的问题是我不确定如何编写符号，所以这是正确的吗？L = {wabcv: v,w ∈ {a,b,c}*}

这个正则表达式接受链的条件是什么？

我最近有一个任务，我必须决定这些语言是否是常规的，或者不是带有引理。

L1 = {xy ∈ {a, b}∗ : |x| = |y|，要么 x 以 a 开头，y 以 ab 结尾，要么 x 和 y 都不是所有 a 的字符串}。

L2 = {xy ∈ {a, b}∗ : |x| = |y|，x 包含子字符串 aa，y 以 ab} 开头。

对于假设泵送长度为 n 的两种语言，我提供了字符串 s = (a^n)(b^n)，因为它满足 L1 的“|x| = |y|，x 以 a 开头，y 以 b 结尾”条件和“|x| = |y|, x 包含子串 aa 和 y 以 a b 开始” L2 的条件。所以，s = x(y^i)z，我选择了 x = (a^n-1)，y = a，z = b^n。对于任何偶数 i，x(y^i)z 中的总字母数是奇数，因此 s 不在 L1 和 L2 中，因为 |x| 不能等于 |y| 了。我只是想知道我做得对还是我错过了什么？

我需要一些帮助来设计接受语言 L= {a^n+1 b^2n c^3n: n>=0} 的图灵机