例 1 :S->bA, A->aA|a 定义了一个什么样的语言?
解: S=>bA=>ba
S=>bA=>baA=>baa
S=>bA=>baA=>baaA=>baaa
……
S=>bA=>baA=> … =>ba …a
L(G1)={ban|n>=1}
L(G1)={ 以 b 开头后跟一个或多个 a 的串 }
例 2 : L(G4)={ambn|m,n 1}
解: S AB
A aA | a
B bB | b
例 3 : L(G5) = {anbn|n 1}
解: S aSb | ab
例 4: ba* —— 所有以 b 开头后跟任意多个 a 的串
(a b)(a b) —— {aa,ab,ba,bb}
(a b) —— { ,a,b,aa,ab …… } 所有由 a 或 b 组成的串
(a|b)*(aa|bb)(a|b)* —— 所有含有两个相继的 a 或两个相继的 b 的串
例 5 : ={a,b} ,则 上所有以 b 开头,后跟若干个 ab 的字的全体所对应的正规式。
b(ab)*
例 6 : ={a,b} ,写出不以 a 开头,但以 aa 结尾的字符串集合的正规式。
b(a|b)*aa
例 7 :将文法 G[S] 转换成正规式
G:S→a A|a
A→dA|d
解:先由产生式得 : S=aA|a A=d*d
将 A 代入 S 中得 : S=ad*d|a
利用正规式变换得 S=a(d*d| ε)=ad*
【说明 :d*d| ε=( ε |d|dd| … )d| ε =d|dd| … | ε = d*】
所求 正规式为 ad*
例 8 :构造与正规式等价的 NFA 示例