作业五
-
（50分）设计一个 DFA，使其接受的串 x x x 满足以下条件：① { x ∣ x ∈ { 0 , 1 } + } \lbrace x|x\in\lbrace 0,1\rbrace^+\rbrace {x∣x∈{0,1}+}；② x x x 包含奇数个 0 0 0；③ x x x 包含子串 111 111 111。
解：对题目进行分析，若对文法要求的 ② 和 ③，分别构造 DFA，会相对容易一些。
识别满足 ① 和 ② 的条件的语言的 DFA 如下所示：
识别满足 ① 和 ③ 的条件的语言的 DFA 如下所示：
因此，结合两个 DFA，同时满足 ①、② 和 ③ 的 DFA 应该有 8 个状态，假设分别为 q 0 , q 1 , q 2 , q 3 , q 4 , q 5 , q 6 , q 7 q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7 q0,q1,q2,q3,q4,q5,q6,q7，前四个状态 q 0 , q 1 , q 2 , q 3 q_0,q_1,q_2,q_3 q0,q1,q2,q3 表示当前处理的输入串中含有 0 的个数为偶数个，且这四个状态分别表示出现了连续 0 , 1 , 2 , 3 + 0,1,2,3+ 0,1,2,3+ 个的 1；后四个状态 q 4 , q 5 , q 6 , q 7 q_4,q_5,q_6,q_7 q4,q5,q6,q7 表示当前处理的输入串含有 0 的个数为奇数个，且这四个状态分别表示出现了连续 0 , 1 , 2 , 3 + 0,1,2,3+ 0,1,2,3+ 个的 1，根据上述定义，不难得出下列的状态函数转移表：
0 1 q 0 q_0 q0 q 4 q_4 q4 q 1 q_1 q1 q 1 q_1 q1 q 4 q_4 q4 q 2 q_2 q2 q 2 q_2 q2 q 4 q_4 q4 q 3 q_3 q3 q 3 q_3 q3 q 7 q_7 q7 q 3 q_3 q3 q 4 q_4 q4 q 0 q_0 q0 q 5 q_5 q5 q 5 q_5 q5 q 0 q_0 q0 q 6 q_6 q6 q 6 q_6 q6 q 0 q_0 q0 q 7 q_7 q7 q 7 q_7 q7 q 3 q_3 q3 q 7 q_7 q7 根据上述状态转移函数，可构造出下列识别该语言的 DFA：
注：其实这里可以构造乘积DFA，具体和子集构造方法差不多
-
（50分）对于文法 G： S → 00 S 1 ∣ 01 S\rightarrow 00S1|01 S→00S1∣01，请问：文法 G 生成的语言 L ( G ) L(G) L(G) 是不是正则语言？若是，请给出具体原因；若不是，请证明你的结论。
解：语言 L ( G ) L(G) L(G) 不是正则语言，利用泵引理证明。
反证法。
显然文法 G 生成的语言为： L ( G ) = { 0 2 n + 1 1 n + 1 ∣ n ≥ 1 } L(G)=\lbrace 0^{2n+1}1^{n+1}|n\ge 1\rbrace L(G)={02n+11n+1∣n≥1}。
假设 L ( G ) L(G) L(G) 是正则语言，那么存在仅依赖于 L ( G ) L(G) L(G) 的泵引理常数 N N N，对于 ∀ z ∈ L \forall z\in L ∀z∈L，如果 ∣ z ∣ ≥ N |z|\ge N ∣z∣≥N，存在 u , v , w u,v,w u,v,w，
不妨令 z = 0 2 N + 1 1 N + 1 z=0^{2N+1}1^{N+1} z=02N+11N+1，那么由 ∣ u v ∣ ≤ N |uv|\le N ∣uv∣≤N 以及 ∣ v ∣ ≥ 1 |v|\ge 1 ∣v∣≥1，可得 u 为全 0 的串组成，v 由全零串或者既有全零串和全1串顺序组合。
不妨设 u = 0 k , 0 ≤ k < N u=0^k,0\le k< N u=0k,0≤k<N，
对 v v v 分类讨论，
-
若 v = 0 j , 1 ≤ j ≤ 2 N − k + 1 v=0^j, 1\le j\le 2N-k+1 v=0j,1≤j≤2N−k+1，那么 w = 0 2 N − k − j + 1 1 N + 1 w=0^{2N-k-j+1}1^{N+1} w=02N−k−j+11N+1，从而
u v 2 w = 0 k 0 2 j 0 2 N − k − j − 1 1 N + 1 = 0 2 N + j + 1 1 N + 1 ∉ L ( G ) uv^2w=0^k0^{2j}0^{2N-k-j-1}1^{N+1}=0^{2N+j+1}1^{N+1}\notin L(G) uv2w=0k02j02N−k−j−11N+1=02N+j+11N+1∈/L(G)
因为 j ≥ 1 j\ge 1 j≥1，所以 u v 2 w ∉ L ( G ) uv^2w\notin L(G) uv2w∈/L(G)，矛盾，根据反证法可得： L ( G ) L(G) L(G) 不属于正则语言。 -
若 v = 0 2 N − k + 1 1 j , 1 ≤ j ≤ N + 1 v=0^{2N-k+1}1^j,1\le j\le N+1 v=02N−k+11j,1≤j≤N+1，那么 w = 1 N − j + 1 w=1^{N-j+1} w=1N−j+1，从而
u v 3 w = 0 k ( 0 2 N − k + 1 1 j ) i 1 N − j + 1 = 0 6 N + 2 k + 3 1 N + 2 j + 1 = 0 2 ( 3 N + k + 1 ) + 1 1 ( N + 2 j ) + 1 uv^3w=0^k(0^{2N-k+1}1^j)^{i}1^{N-j+1}=0^{6N+2k+3}1^{N+2j+1}=0^{2(3N+k+1)+1}1^{(N+2j)+1} uv3w=0k(02N−k+11j)i1N−j+1=06N+2k+31N+2j+1=02(3N+k+1)+11(N+2j)+1只需要判断 3 N + k + 1 = N + 2 j ( ∗ ) 3N+k+1=N+2j(*) 3N+k+1=N+2j(∗)，显然 (*) 式不成立，因为 2 N + k + 1 = j 2N+k+1=j 2N+k+1=j，结合 1 ≤ j ≤ N + 1 1\le j\le N+1 1≤j≤N+1 以及 0 ≤ k < N 0\le k<N 0≤k<N 可得， 2 N + k + 1 > N + 1 ≥ j 2N+k+1>N+1\ge j 2N+k+1>N+1≥j，因此等式不成立，所以 u v 3 w ∉ L ( G ) uv^3w\notin L(G) uv3w∈/L(G)，矛盾，根据反证法可得： L ( G ) L(G) L(G) 不属于正则语言。
综上所述， L ( G ) L(G) L(G) 不属于正则语言。
-
矛盾，根据反证法可得： L ( G ) L(G) L(G) 不属于正则语言。
综上所述， L ( G ) L(G) L(G) 不属于正则语言。