新春快乐！ 顺便请教个中学数学题目

幻の上帝

虽厉……这叫中学数学题目吗……
想得通有2^x（x是epsilon的个数）个副本，不过想不出来“配置”中副本之间的约束……

cjaizss

captivated 发表于 2013-02-09 14:10
ok, 继续。

我们采用前述介绍的第二种模型，也就是每当需要进行非确定性选择时克隆自身。在任一时刻，存 ...

“在任一时刻，存在NFA克隆副本活动状态的那些集合称为NFA的配置。”
意思是，还活着的线程？

captivated

回复 12# cjaizss


    嗯，状态转移正确的继续往后匹配，否则那个线程就死掉了，只有活下来的线程能继续匹配。活下来的每个线程遇到epsilon转移的时候又克隆自身。由于状态最多只有N个，每个状态的epsilon转移属于 2 ^ N(N个状态的幂集)。我想不通的是为什么最大配置数(整个匹配过程中最多能够存活的线程数)是 |sigema| ^ N

cjaizss

captivated 发表于 2013-02-17 12:24
回复 12# cjaizss

没想明白啊，或者我审题错误
如果我没想错，以下是不是可以有任意多进程？
1 ->(起点状态、接受状态）
2 | a epsilon  
3 | b
------------
2->
1 | b
3 | a
------------
3->
1 | a
3 | b

captivated

回复 14# cjaizss


    哦，第三个图和正则表达式a*ab等价的，第一个图和第二个图分别等价于正则表达式a*和ab. 我都画一张里面，你可能没注意，第三个图起始状态不是接受状态，只有标蓝色的圆圈才是接受状态。

    a*ab可以适配单词ab, 那正则表达式中的a*就相当于没从输入流中取东西, 直接从s0开始一个空的epsilon转移到了s1, 就是不从输入流中取字符它就自己转移了. 接下来s1状态从输入流中取出a, 转移到s2, 然后s2状态了从输入流中取出b, 转移到s3, 此时输入流耗尽，s3是接受状态，因此这个自动机接受字符串/单词ab.

    a*ab也可以适配单词aab. 那这样子s0的时候，从输入流中取出a, 转移到s0自己。接下来不从输入流取字符, 空转移到s1. 然后s1 -- a --> s2, s2 -- b --> s3, 这时输入流耗尽，自动机也正好处于接受状态，所以这个自动机也接受字符串aab.

    当处于s0的时候，这时输入流中剩下的字符串是什么样子自动机是不知道的，自动机只能看到输入流中最前面的那个即将读取的字符。该怎么转移是由整个字符串决定的。
    就像 ab 和 aab 两个单词, 自动机一开始处于起始状态s0, 此时自动机能看到的只是字符a，但是ab和aab, aaab等等这些字符串自动机都应该接受，而且是必须在输入流刚好耗尽时自动机刚好处于接受状态。
    那在s0的时候自动机怎么知道该空转移到s1, 还是从输入流中读取字符a转移到s0呢？这是字符a后面剩下的字符串决定的。
    那么在s0的时候自动机就面临两个选择: 不从输入流中取字符，空转移到s1; 或者从输入流中取字符a, 又转移到s0. 只要还在s0这个状态, 自动机都面临该怎么转移的选择，每次都要，该转移到那一个，在只看到输入流的最前面的字符的时候是不确定的，所以才叫非确定型自动机。所以处理的方式就是贴中说的，要么先选一个转移匹配下去，等到错了又回头从来；要么在s0的时候我就两个都选，单线程变双线程，能继续匹配下去的线程就存活，不能继续匹配的就死掉，只要输入流耗尽了最终还有存活的线程，而且该线程自动机状态又恰好处于接受状态的时候，自动机接受该输入流/字符串。

    由于空转移也不是限定只能有一个的，不同的正则表达式和不同的转移图/自动机等价。有时候在某个状态的时候可以空转移到几个另外的状态。假设一个自动机有N个状态，从某个状态能空转移到的状态数肯定不超过N，所以不论任何状态，它能[通过空转移]转移到的状态是一个状态集合，这个集合属于N个状态的幂集合，就是2 ^ N。这个是肯定的。不过为什么（不论任何NFA）其配置数在任意时刻最大是|Sigema| ^ N, 就一直没想通。。。

captivated

回复 11# 幻の上帝


    嗯。我也是啊。书上只给了结论，没给任何提示或者证明。以前看的时候没认真，觉得书上那么说就是那样。然后最近由于某种原因想要自己实现一个手工词法分析器(更确切滴说更像是一个词法分析器生成器，像flex那样)。本来借助flex就好，我想自己写，这个词法分析器要能自己分析正则表达式，就像flex那样(我没看过flex源码，也不知道它怎么实现的，不过我的需求不像flex那样要考虑那么多，就是自己能用就行，所以实现难度不算很高)。编码是先解析正则表达式，使用thompson构造法构造NFA，然后NFA转DFA，DFA最小化，然后DFA判定的。本来按流程做也没什么，因为词法分析器最终是DFA判定。不过因为这个我重新看了本书，看的时候就有了这个疑问了

  PS，新年快乐哈。

cjaizss

captivated 发表于 2013-02-17 17:55
回复 14# cjaizss

我那个是我自己构造的NFA,只有三个状态,似乎可以制造出任意多的进程并长期不死.
但似乎这个不能由任何RE经过那个叫啥啥啥的算法生成.

captivated

回复 17# cjaizss


    哦 我明白了。你画的那个图似乎是状态1通过a和epsilon转移到状态2， 这样应该不行，不能构建等价的正则表达式，就是说这个状态机超出了一般等价于正则表达式的有限状态机的范畴

captivated

回复 17# cjaizss

晕 不好意思没仔细看 我想想
不可能长期不死的 因为有个前提是被判定的字符串长度是有限的 因为输入流是有限的 输入流耗尽所有线程都得死 只是这个时候要判定线程中是不是有自动机处于接受状态 如果有就接受字符串 如果没有就不接受字符串～

cjaizss

captivated 发表于 2013-02-17 20:41
回复 17# cjaizss

晕 不好意思没仔细看 我想想

我那个NFA每个都接受a,b
只要你输入永远是a,b,就不会有进程死
而每次到了状态1,都可以直接fork epsilon成状态2