Re: [理工] [離散] 有限狀態機language觀念問題
看板Grad-ProbAsk作者DavyBlue (Nothing at all)時間15年前 (2011/03/13 17:39)推噓1(1推 0噓 7→)留言8則, 3人參與討論串2/2 (看更多)
好久以前學的了 不確定對不對
有錯請指正
※ 引述《ms70831 (YO-YO-TV)》之銘言：
: 想要問一下
: (1)context-free
上下文無關文法
你就記得是左邊只有非終端符號
右邊可以是非終端或終端符號
ex:
S->Aa
A->a
: (2)context-sensitive
上下文有關文法
左右都可以有終端符號
ex:
aSa->aAAa|aRa
aAAa->abba
aR->aa
之類的 我隨便舉的例子
那種a^n b^n c^n的東西都只有CSG造得出來
: (3)regular
必須要可以用有限狀態機造出來 DFA NFA都可以
文法的話必須符合
左邊只能有一個非終端符號
右邊第一個一定是終端符號或空字串
三者大小是3包含於1包含於2
: 這幾個該怎麼分??
: 看了書之後還是有點不太了解><!!
: 希望有大大可以用簡單的概念解釋一下
: EX.Is the language (a) L1 = {a^nb^n | n = 1,2,3,.....}
(1)(2)
S->aSb | 空字串(不會打)
: (b) L2 = {a^nb^nc^n | n = 1,2,3,...}
(2)
這個文法要寫出來很長 GOOGLE看看吧wiki應該有
: (C) L3 = {b^nab^n | n = 0,1,2......,m = 1,2,3......}
(1)(2)
S->bSb
S->a
這個我不確定能不能轉成正規 其實我印像中可以
可是想不出來囧
我先說我不確定我說的是對的XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.213.63
→
03/13 17:46, , 1F
03/13 17:46, 1F
→
03/13 17:46, , 2F
03/13 17:46, 2F
→
03/13 19:25, , 3F
03/13 19:25, 3F
→
03/13 19:28, , 4F
03/13 19:28, 4F
→
03/13 19:30, , 5F
03/13 19:30, 5F
→
03/13 19:33, , 6F
03/13 19:33, 6F
→
03/13 19:36, , 7F
03/13 19:36, 7F
推
03/13 21:37, , 8F
03/13 21:37, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：