代码之家 › 专栏 › 技术社区 › h3rm8

如何为给定的DFA在一组q状态上提出递推方程?

formal-languages dfa finite-automata recurrence combinatorics

0

h3rm8 · 技术社区 · 10 年前

我试图通过以下链接解决问题2: Check out Q.2 .

那就是我对号码感兴趣 N(k) 长度为的二进制字符串 k 被以下确定性有限自动机接受(来源:URL)。

例如 N(2)=2 ,因为只有这样的字符串 01 和 10 。特别是,我对以下的循环关系感兴趣 N(k) .

1 回复 | 直到 10 年前

1

2

blazs 10 年前

复发是 N(k) = 2*N(k-3) + N(k-2) 对于 k>=3 ,具有边界条件 N(0)=N(1)=0 和 N(2)=2 .

原因是给定一个可接受的字符串 w (可接受的意思是DFA接受的字符串),您可以使用 11 “保持”在最终状态或添加 010 或 001 (长度均为3)“保持”在最终状态;这些观察结果直接导致了这种复发(想想看)。

举个例子,下面是长度的前几个字符串 k=2,3,...,7 被自动机接受:

对于k=2,解为 01 , 10 .
对于k=3,没有解。
对于k=4,解为 0111 , 1011 .
对于k=5,解为 01001 , 01010 , 10010 , 10001 .
对于k=6,解为 011111 , 101111 .
对于k=7,解为 0100111 , 0101011 , 1001011 , 1000111 , 0111001 , 0111010 , 1011001 , 1011010 .

我们可以看到,递归正确地计算了解决方案的数量:

N(3)=2*N(0)+N(1)=2*0+0=0。
N(4)=2*N(1)+N(2)=0+2=2。
N(5)=2*N(2)+N(3)=2*2+0=4。
N(6)=2*N(3)+N(4)=2*0+2=2。
N(7)=2*N(4)+N(5)=2*2+4=8。