[工學(xué)]形式語言與自動機(jī)07章正則語言的性質(zhì)-資料下載頁
2024-10-18 23:57本頁面
【正文】 N個狀態(tài)的有限狀態(tài)自動機(jī) ，若串 z∈ L(M)， 且 |z|≥N， 則 z能夠記為 uvw，且對所有的 i≥0， 串 uviw∈ L(M)。 注意 ?利用右線性語言的泵浦引理，可以證明某些語言不是右線性語言，即用反證法證明語言不滿足泵浦引理。 例 75 ?證明 {0n1n| n?1}不是 RL。 證明：令 L= {0n1n| n?1} 。假設(shè) L是 RL，則它滿足泵引理。不妨設(shè) N是泵引理中僅依賴于 L的正整數(shù)，取 z = 0N1N，顯然 z?L 此時必然 ?u, v, w st. z = uvw, |uv| ? N , |v| ? 1， 因此 v只可能是由 0組成的非空串 設(shè) v=0k ， k ? 1 。 w = 0j1N 則 u = 0Nkj 例 75(續(xù) ) ?從而有 uviw = 0Nkj (0k)i0j1N 當(dāng) i = 2時， uv2w = 0Nkj 02k0j1N = 0N+k1N 由于 k ? 1 ， N+kN 也就是說， uv2w?L，這與泵引理矛盾。 所以， L不是 RL 例 73 ?證明 {0n| n為素數(shù) }不是 RL。 簡證：假設(shè)它為 RL，且有一個長度為N+p(取這樣的長度是為了保證其 ?N)的串，則可以有長度為 k的 0串可以被隨意地泵進(jìn)， N+p+ik均保持為一個素數(shù)，顯然，當(dāng) i= N+p 時 N+p+ik = (N+p)(k + 1) 為一個合數(shù)。矛盾。因此它不是 RL。 例 74 ?證明 {0n 1m 2n+m | m, n ? 1}不是 RL。 證明：令 L= {0n 1m 2n+m | m, n ? 1} 。假設(shè) L是 RL，則它滿足泵引理。不妨設(shè) N是泵引理中僅依賴于 L的正整數(shù)，取 z = 0N1N22N，顯然 z?L 此時必然 ?u, v, w st. z = uvw, |uv| ? N , |v| ? 1， 因此 v只可能是由 0組成的非空串 設(shè) v = 0k ， k ? 1 。 w = 0j1N22N 則 u = 0Nkj 例 74(續(xù) ) 從而有 uviw = 0Nkj (0k)i0j1N22N 當(dāng) i = 0時， uv0w = 0Nk1N22N 由于 k ? 1 ， Nk + N 2N 也就是說， uv0w?L，這與泵引理矛盾。 所以， L不是 RL 作業(yè) ?習(xí)題 5(1)(2)(3)(8)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1