[理工] 離散

看板Grad-ProbAsk作者 (微笑的故事)時間11年前 (2012/09/22 23:03), 編輯推噓1(1推 0噓 6→)
留言7則, 2人參與, 最新討論串6/22 (看更多)
請教各位大大 小黃書下冊13—49頁 證明語言L={a^k * b^k |k>=1}不為有限狀態語言 -- posted from android bbs reader on my samsung GT-I9003 https://market.android.com/details?id=com.bbs.reader -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 110.28.251.81
推
09/23 00:29, , 1F
若L為有限狀態語言,則存在有限狀態機M認知L,設其有n個狀態
09/23 00:29, 1F
→
09/23 00:30, , 2F
考慮字串d=a^n*b^n,設此字串輸入到被接受的狀態變化為:
09/23 00:30, 2F
→
09/23 00:30, , 3F
S0->S1->....->Sn->.....->S2n,則S0~Sn有n+1個狀態,
09/23 00:30, 3F
→
09/23 00:32, , 4F
故存在Si=Sj,i=/=j
09/23 00:32, 4F
→
09/23 00:32, , 5F
代表存在一更短路徑字串a^m*b^n,m<n而被接受,
09/23 00:32, 5F
→
09/23 00:32, , 6F
與L={a^k*b^k |k>=1}不合
09/23 00:32, 6F
→
09/23 12:45, , 7F
懂了！感謝d大！
09/23 12:45, 7F
‣ 更多 bouwhat 的文章
文章代碼(AID): #1GNTCiT7 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 6 之 22 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
0
3
[理工] 離散 離散
thank1984
15年前, 03/22
理工
2
6
[理工] 離散 離散
showyoulovex
12年前, 11/27
理工
3
3
[理工] 離散 離散
showyoulovex
12年前, 11/30
理工
2
2
[理工] 離散 離散
jerrywings
12年前, 05/02
理工
0
5
Re: [理工] 離散 Re: 離散
mei383
12年前, 05/03
理工
1
7
[理工] 離散 離散
bouwhat
11年前, 09/22
理工
7
22
[理工] 離散 離散
naoh810322
10年前, 02/08
理工
1
1
Re: [理工] 離散 Re: 離散
kiki86151
10年前, 02/08
理工
0
1
Re: [理工] 離散 Re: 離散
leosnake
10年前, 02/08
理工
1
2
[理工] 離散 離散
AgentSkye56
9年前, 07/09
在新視窗開啟完整討論串 (共22篇)
‣ 更多 bouwhat 的文章
文章代碼(AID): #1GNTCiT7 (Grad-ProbAsk)