新春快樂！ 順便請教個中學(xué)數(shù)學(xué)題目

captivated

    是關(guān)于NFA的兩種處理模型的.

    NFA不同于DFA，在于其引入了epsilon轉(zhuǎn)移，因此，當(dāng)NFA處于某個具有epsilon轉(zhuǎn)移的狀態(tài)，并且處于輸入流上的某個點時，實際上NFA需要對剩下的輸入流做一個猜測。

    考慮正則表達(dá)式 a*ab:
   
    figure 1

    figure 1中, 藍(lán)色圓圈標(biāo)明的狀態(tài)為接受狀態(tài).

    RE a*ab可以匹配 ab, aab, aaab, aaaab, aaaaab,... etc.
    epsilon轉(zhuǎn)移的引入，使得在狀態(tài)s0遇到輸入字符a時, NFA可以采取兩種不同的轉(zhuǎn)移: s0 ---epsilon---> s1,    or s0---a--->s0.
    也即, 當(dāng)處于狀態(tài)s0時, NFA需要“猜測”正確的轉(zhuǎn)移： 根據(jù)剩下的輸入流，應(yīng)該轉(zhuǎn)移到s0呢，還是轉(zhuǎn)移到s1?

    對于NFA的這種"猜測"的處理，歷史上有兩種基本模型。
    1) 每次NFA必須進(jìn)行非確定性選擇時，如果有使得輸入字符串轉(zhuǎn)向接受狀態(tài)的轉(zhuǎn)移存在，則采用這樣的轉(zhuǎn)移。如果從編碼的角度來說，就是先采用某個轉(zhuǎn)移，然后繼續(xù)匹配下去，當(dāng)耗盡輸入流時仍未到達(dá)接受狀態(tài)，或者繼續(xù)匹配導(dǎo)致轉(zhuǎn)移到錯誤狀態(tài)，那么就回溯到開始的需要進(jìn)行非確定性選擇的狀態(tài)，選擇另一個轉(zhuǎn)移繼續(xù)試探。簡單地說就是試探--回溯。這個模型導(dǎo)致，如果我們使用這個NFA模型來設(shè)計詞法匹配，那么這個詞法匹配算法不是O(n)的(現(xiàn)在的詞法分析器都是O(n)的；但是那是把NFA轉(zhuǎn)換為DFA，然后根據(jù)DFA構(gòu)建的詞法分析器。這里討論的是，假設(shè)直接在NFA上構(gòu)建詞法匹配算法的第一種模型)。
    2) 每次NFA必須進(jìn)行非確定性選擇時，NFA都克隆自身，以追蹤每個可能的轉(zhuǎn)移。在這個模型中，NFA并發(fā)地追蹤所有轉(zhuǎn)移路徑。可以想象，從這個需要進(jìn)行非確定性選擇的狀態(tài)開始，所有屬于 該狀態(tài)的epsilon-closure集合 的狀態(tài)都被克隆，每個克隆都是從原來的“主線程” fork or clone 出來的線程，每個線程都追蹤剩下的輸入流。當(dāng)耗盡輸入流仍未到達(dá)接受狀態(tài)或者繼續(xù)匹配導(dǎo)致轉(zhuǎn)移到錯誤狀態(tài)，那么該線程自然死亡。這種想法也是NFA轉(zhuǎn)換為DFA的“子集構(gòu)造”算法的基本出發(fā)點。假設(shè)每次fork出來的線程都有相應(yīng)的資源來處理的話，那么顯然這個算法是O(n)的(事實上，我們假設(shè)直接真的用多線程來處理這個，很顯然不太可能出來個線程就分配個CPU物理線程給用，所以實際上它仍然不是O(n)的，某種程度上，說“多線程O(n)算法”，就意味著這個算法實際上不是O(n)的。所以實際上編譯器采用的詞法分析器都是將NFA轉(zhuǎn)換為DFA，然后構(gòu)建O(n)算法的)。

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

ok. 這個是引子介紹，我要請教的問題不是這個，當(dāng)然問題也不困難，只是我腦袋搭鐵迷糊了，請廣大CUer幫忙解答下罷～樓下繼續(xù)。

=======================
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, 繼續(xù)。

我們采用前述介紹的第二種模型，也就是每當(dāng)需要進(jìn)行非確定性選擇時克隆自身。在任一時刻，存在NFA克隆副本活動狀態(tài)的那些集合稱為NFA的配置。當(dāng)NFA到達(dá)一個配置，此時NFA已經(jīng)耗盡輸入流，且配置中的一個或多個克隆副本處于某個接受狀態(tài)時，則NFA接受該輸入流（為合法的單詞/字符串）。

question 1: 具有n個狀態(tài)的NFA，最多會產(chǎn)生 |Sigema| ^ n 個配置(sigema是字母表。希臘字母打印不便你懂的)。求解釋，求證明。最好是構(gòu)造性證明，也即，能夠構(gòu)造出具有這樣的最大配置數(shù)的NFA嗎？如果能，那么它長什么樣？有RE嗎? 請畫出轉(zhuǎn)移圖。

captivated

回復(fù) 2# folklore


    嗯。我還正要@你呢。算法我已經(jīng)給了。我的問題不是如何編碼處理NFA。問題在你回復(fù)的樓下。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 發(fā)表于 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 “構(gòu)形” or “組態(tài)” 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

回復(fù) 5# folklore


    Thanks for your reply. Let me think a bit~

    Best wishes for a wonderful chinese new year!

captivated

回復(fù) 7# Ager


    HoHo, Best wishes for chinese new year~

    about the translation of "configuration", surely "構(gòu)型" or "組態(tài)" is more appropriate.

    Thanks for your reply, Let me think a bit,