Re: [理工] [離散] 有限狀態機language觀念問題

[DavyBlue (Nothing at all)]

好久以前學的了 不確定對不對
有錯請指正
※ 引述《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
→ DavyBlue:我知道了 你的C題目給錯 後面應該是b^m 這樣就有辦法寫
→ DavyBlue:所以C應該是123都是 如果是單選就選最小的那一個3
→ antiasus:1) n不為0不會有ε,至少會有ab
→ antiasus:rule直接用ε的話會產生空字串.
→ antiasus:不過維基是這麼寫就是,或許是我想錯.
→ antiasus:我的想法: S -> aSb | ab   (因為n>=1,>=0才可以用ε)
→ DavyBlue:你應該是對了 我少想這部分
推 ms70831:沒錯!!是b^m次我了解了謝謝兩位大大