computation-theory

2热度

1回答

我有一个关于这个问题一个问题：鉴于ň城市C1，C2，...，CN：构建的成本市电站Ci是pi。造城运动词和CJ之间无向电力线路成本w_ij。鉴于所有费用PI，w_ij，德兴多项式算法寻找最小成本集供电线路的连接词到另一个城市，发电站。你有什么想法我该如何解决这个问题？我一直在想动态规划这样的东西，还有一些像“如果城市Ci没有发电站，那么它需要一个连接到另一个城市，所以我们可以找到所有j

1热度

1回答

DFA代表密码

我想设计一个DFA密码认为有以下限制：它必须是8个字符长它必须包含至少两个小写字符：[a-z] 它必须包含至少一个大写字符：[A-Z] 它必须包含至少两个十进制数：[0-9] 它必须包含至少一个这些特殊字符：[[email protected]*_] 它必须以特殊字符如何设计这个DFA开始？

1热度

2回答

{w |在w的每个奇数位置是1}

任务是在字母{0,1}上为此语言构建DFA。我构建了一个由4个状态组成并且不接受空白字的DFA。然而，在答案中，他们给出了一个接受它的3状态DFA。为什么我的DFA会接受一个空的单词，如果在空单词中没有1在奇数位置，这意味着它不在该语言中？

0热度

1回答

抽象引理是什么，你如何做？

所以我有一个抽吸引理问题A{www|w ∈ {a,b}*} 我有正确的答案，但我不完全确定它是如何工作的。我给的答案只是让人们知道我会与假设A是REG 设P为抽长 x ∈ A, x=a^p b, a^p b, a^p b .... |s|=3p+3 其中每个a^p b是AW 令S = XYZ使得 1分裂）sum of i>=0s'=xy'z ∈ A 2）|x|>0，3）|xy| <=p 通过（3

0热度

1回答

感应字符串？（自动相关）

老实说，我所知道的关于数学归纳法是如下： 1. prove P(0) - base step 2. for all n ≥ 1, prove (P(n − 1) -> P(n)) - inductive step And here is image of my induction problem that I am struggling now (please click) 目前我正在试图解

1热度

1回答

字符串的前缀

如果x不等于y，则x是字符串y的前缀，如果存在xz = y且x是合适的前缀。只是想确保我正确理解这个概念。例如，如果有字符串y =“abracadabra”是否意味着有可能的前缀负载？所以，如果x是一个前缀，那么x可以等于“a”，“ab”，“abr”或甚至“abracadabra”，但在这种情况下，当x = y时，它现在称为不正确的前缀，据我所知。但是，我不确定最后一部分x = y是否仍然

0热度

1回答

想知道下推自动机解决方案是否正确

我有一个问题说：构建一个接受语言{a^i b^j | 0 < =我< = j的} ，这是给定的解决方案： δ (q0, a, z) = (q0, az) read a, push a δ (q0, a, a) = (q0, aa) δ (q0, b, a) = (q1, λ) read b, pop a δ (q1, b, a) = (q1, λ) δ (

1热度

1回答

无法理解解决方案（图灵机与缩减）

Please click this to see my problem 嗨。关于这个问题，我只是不明白其提供的解决方案。我们知道的ATM补= {<M,W>：M是TM和M不接受白}如照片的描述和RTM = {<M,W>：M是TM是拒绝输入列W} 如果我们把M,epsilon到每个以上， the complement of Atm = M does not accept epsilon Rtm

1热度

1回答

寻找加权无向图中固定成本的路径？

我有以下问题，我不太清楚如何解决这个问题：给定图G = (V;E)其中每一条边有一个正整数成本c_e和起始顶点s\in V。设计一个O(V + E)算法，使用路径（不一定是简单的路径）与路径总成本的5 是倍数可达标志着所有顶点从s我怎么可以跟踪的成本总额的我已经访问过的路径？我一直在研究有向图中的BFS，并在这里尝试了一些尝试，但大多数BFS参考文献的重点是找到最短路径（而不是像保持5的倍数）。

0热度

2回答

需要构造DFA（确定性有限自动机）

我需要构造一个DFA，它可以识别所有由0和1完全构成的字符串，以便它有偶数个零和可以被3整除的个数。我发现自动为偶数0和偶数个1的情况下：我试图从这里去添加一些国家，改变分支机构，等等。不过我仍然不成功通常无法追踪的有什么自动机做我会补充的分支和状态。任何帮助将不胜感激。