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

captivated

    是关于NFA的两种处理模型的.

    NFA不同于DFA，在于其引入了epsilon转移，因此，当NFA处于某个具有epsilon转移的状态，并且处于输入流上的某个点时，实际上NFA需要对剩下的输入流做一个猜测。

    考虑正则表达式 a*ab:
   
    figure 1

    figure 1中, 蓝色圆圈标明的状态为接受状态.

    RE a*ab可以匹配 ab, aab, aaab, aaaab, aaaaab,... etc.
    epsilon转移的引入，使得在状态s0遇到输入字符a时, NFA可以采取两种不同的转移: s0 ---epsilon---> s1,    or s0---a--->s0.
    也即, 当处于状态s0时, NFA需要“猜测”正确的转移： 根据剩下的输入流，应该转移到s0呢，还是转移到s1?

    对于NFA的这种"猜测"的处理，历史上有两种基本模型。
    1) 每次NFA必须进行非确定性选择时，如果有使得输入字符串转向接受状态的转移存在，则采用这样的转移。如果从编码的角度来说，就是先采用某个转移，然后继续匹配下去，当耗尽输入流时仍未到达接受状态，或者继续匹配导致转移到错误状态，那么就回溯到开始的需要进行非确定性选择的状态，选择另一个转移继续试探。简单地说就是试探--回溯。这个模型导致，如果我们使用这个NFA模型来设计词法匹配，那么这个词法匹配算法不是O(n)的(现在的词法分析器都是O(n)的；但是那是把NFA转换为DFA，然后根据DFA构建的词法分析器。这里讨论的是，假设直接在NFA上构建词法匹配算法的第一种模型)。
    2) 每次NFA必须进行非确定性选择时，NFA都克隆自身，以追踪每个可能的转移。在这个模型中，NFA并发地追踪所有转移路径。可以想象，从这个需要进行非确定性选择的状态开始，所有属于 该状态的epsilon-closure集合 的状态都被克隆，每个克隆都是从原来的“主线程” fork or clone 出来的线程，每个线程都追踪剩下的输入流。当耗尽输入流仍未到达接受状态或者继续匹配导致转移到错误状态，那么该线程自然死亡。这种想法也是NFA转换为DFA的“子集构造”算法的基本出发点。假设每次fork出来的线程都有相应的资源来处理的话，那么显然这个算法是O(n)的(事实上，我们假设直接真的用多线程来处理这个，很显然不太可能出来个线程就分配个CPU物理线程给用，所以实际上它仍然不是O(n)的，某种程度上，说“多线程O(n)算法”，就意味着这个算法实际上不是O(n)的。所以实际上编译器采用的词法分析器都是将NFA转换为DFA，然后构建O(n)算法的)。

=======================

ok. 这个是引子介绍，我要请教的问题不是这个，当然问题也不困难，只是我脑袋搭铁迷糊了，请广大CUer帮忙解答下罢～楼下继续。

=======================
update: s0---epsilon---> s1, 之前写错.

folklore

1. translate a*ab to a+b (but it seems difficulty, but if you can detect the "collicision", just as you descripted, it is not a promble)
2. look ahead one more token, but it actually is not able to handle all collicision case...

captivated

ok, 继续。

我们采用前述介绍的第二种模型，也就是每当需要进行非确定性选择时克隆自身。在任一时刻，存在NFA克隆副本活动状态的那些集合称为NFA的配置。当NFA到达一个配置，此时NFA已经耗尽输入流，且配置中的一个或多个克隆副本处于某个接受状态时，则NFA接受该输入流（为合法的单词/字符串）。

question 1: 具有n个状态的NFA，最多会产生 |Sigema| ^ n 个配置(sigema是字母表。希腊字母打印不便你懂的)。求解释，求证明。最好是构造性证明，也即，能够构造出具有这样的最大配置数的NFA吗？如果能，那么它长什么样？有RE吗? 请画出转移图。

captivated

回复 2# folklore


    嗯。我还正要@你呢。算法我已经给了。我的问题不是如何编码处理NFA。问题在你回复的楼下。Thanks.

folklore

in actually my math is very poor. @cjaizss

proof:
set alpha = the token dictory that nfa can accept
let alphas =a list of all token that the nfa accepts
you can define a regular exp such as:
[alphas]{0, the size of alphas} \<< repead it n times\ [alphas]{0, the size of alphas}

i think the above exp generating |Sigema| ^ n  nfa copies.

captivated

@幻の上帝
@starwing83
@Ager

Ager

captivated 发表于 2013-02-09 14:27
@幻の上帝
@starwing83
@Ager

Well, let me have a Chě:

As to the concept “configuration” you mentioned, also means the instantaneous description of a certain NFA, and I prefer to translate it with “构形” or “组态” but NOT “配置” since the latter Chinese word actually means “an action of setting upon some configuration”.

A “configuration” of a finite-state automaton M<Q,Σ,σ,s,F> should metaphysically be a singleton uqv like a dimensional formula in physics: q is a single one of states in Q, and uv is a string in Σ*. So, a configuration of M, either DFA or NFA, should be expressed as a word in QΣ*.

The method of “configuration” is frequently used in the process so-called “Powerset/Subset construction”: Be aware that NFA always has the finite numbered clones, that is to say, this number of “configuration” must be bounded ---  a piece of “configuration” either refers to a certain clone in that state or nothing to be referred to. Therefore, if this NFA has n states, it should play at most 2^n  configurations, that is a basic fact due to Powerset/Subset construction we play.

Furthermore, if we perform the behavior of a NFA, it should need a DFA who has a single state for EACH “configuration” of the former NFA. Now we denote the set of ALL Subsets of N as:

2^^N

So, this DFA's Q should be at most 2^^(NFA's Q). As we know, 2^^(NFA's Q) is finite. So, we always perform a behavior of DFA with a finite procedure which time is always consumed by a linearly growth with the length of input string.

Now we call a NFA<N,Σ,σ,n,f> as “渣”.

渣 has a certain number of “configuration”s NO more than

| 2^^N |

Well, stop here, on this great night. More stuff about so-called “proof” and/or “pseudo-/code” MAY come soon.

F-Y-I, He-he... Happy Chinese New Year {:3_193:}

346196247

好吧cu的c版，改成english交流，我虽然中文english都不好，

captivated

回复 5# folklore


    Thanks for your reply. Let me think a bit~

    Best wishes for a wonderful chinese new year!

captivated

回复 7# Ager


    HoHo, Best wishes for chinese new year~

    about the translation of "configuration", surely "构型" or "组态" is more appropriate.

    Thanks for your reply, Let me think a bit,