正规文法、正规表达式、有限自动机及其之间的转换（笔记）-Toy模板网

这篇具有很好参考价值的文章主要介绍了正规文法、正规表达式、有限自动机及其之间的转换（笔记）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

The Equivalent Transforming among RG, RE and FA

正规文法

A Grammar G is a quadruple (四元组):G = (V_N, V_T, S, P )

Where,

V_N is a finite set of nonterminals.
V_T is a finite set of terminals.
S is the start symbol, S $\in$ V_N.
P is a finite set of productions (产生式).

Regular Grammar (RG) (正规文法):

α∈V_N and β ∈V_T∪V_TV_N

正规表达式

Regular Expression:

Regular expressions over ∑ are defined as :

ε and $\phi$ are RE’s, denoting the sets {ε} and Φ , respectively ;
Any a $\in$ ∑ , a is an RE, denoting the set { a };
If a and b are RE’s, denoting the sets A and B respectively, then a b , a | b, and a* are RE’s, denoting the sets AB, AUB and A* respectively;
Nothing is an RE unless it follows from 1 to 3 finite times.

有限自动机

确定的有限自动机

Deterministic Finite Automata:

A Deterministic Finite Automaton (DFA) is a quintuple (五元组)

M = (S, ∑ , f, s₀ , Z),

where

S is a finite set of states;
∑ is the set of input symbols;
f : S×∑ →S, the transition function;
s₀ $\in$ S, the initial state;
Z $\subseteq$ S, the set of final states.

非确定有限自动机

Nondeterministic Finite Automata:

An Nondeterministic Finite Automata (NFA) is also a quintuple

M = ( S, ∑ , f, s₀ , Z),

where:

S is a finite set of states;
∑ is the set of input symbols;
f : S×∑* →ρ(S), the transition function;
s₀ $\in$ S, the initial state;
Z $\subseteq$ S, the set of final states.

Difference between DFA & NFA

The definitions of transition functions of DFA and NFA are different:

DFA f: S×∑ →S

NFA f: S×∑* →ρ(S)

That means: a state of DFA has a unique next state and can not transit without input, but a state of NFA may have more than one next states and can transit without input.

正规表达式转换为正规文法

Transforming RE to RG

Let r be an RE on∑. Construct G = (V_N, V_T, S, P):

Initialization: V_T＝∑; P = {S → r}; V_N ={S};
For any production in P, rewrite it as follows:

⑴ A → x*y => A → xA |y.

⑵ A→x | y => A → x | y;

⑶A → xy => A → xB B → y; V_N = V_N ∪{B};

⑷A→(x | y)B =>A → xB | yB; V_N = V_N ∪{B};

where x and y be RE’s, B be a new nonterminal.
Repeat step 2 until each rule has one termianal.

样例

Transform a(a | d)* to RG

V_T＝{a, b}; P = {S → a(a | d)* }; V_N ={S};

S → a(a | d)* => S → aA A → (a | d)*

A → (a | d)* => A → (a | d)A |ε

A → (a | d)A => A → aA | dA

Finally we get the regular grammar G is

({S, A}, {a, b}, S, {S→ aA A→ aA|dA|ε})

正规文法转换为正规表达式

Transforming RG to RE

Transform RG to a group of equations by replacing → and | as = and +, respectively.
For equations X = aY + a and Y = b, we replace Y by b, and get X = ab + a.
If there is an equation X=rX + t, we have the solution X = r*t;
Repeat step 2 and 3, until the solution S=r is got. Then r is the corresponding RE.

样例

Consider the grammar G:S → aS | aA A → bB B → aB | a

Transform the rules into a group of equations:

S = aS + aA (1)

A = bB (2)

B = aB + a (3)
For equation 3 we have: B = a*a;
For equation 2 we have: A = ba*a;
For equation 1 we have: S = aS + aba*a;
Finally we have: S = a*aba*a;