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

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:}