在解題之前, 先來複習一下Grammar吧!
V: 所有states (被使用在Grammar裡的)
T: alphabet, 例: {a,b}
S: V中的其中一個, 起始state
P: 終止state
- - -
描述正規語言的方法 (1)automata自動機 (2)Rex正規表示式 (3)Grammar
Grammer是其中一種, 換言之, Grammar可以與automata和rex互相轉換
一個Grammar分成left-linear和right-linear
right-linear: (產生的string由左往右堆疊, 就像一般的書寫習慣)
A->xB
A->x
left-linear: (產生的string由右往左堆疊)
A->Bx
A->x
其中A,B屬於V, (A,B是states)
x屬於T* (x是一個字元組合,字串)
- - -
例:
A->aaaB (right-linear)
A->λ
B->λ
等同於 (aaa)*
也可寫成:
A->aaaB
A|B->λ
或:
A->aaaB|λ
B->λ
"|"是"or"的意思
- - -
right-linear所畫出來的automata和寫出來的rex是我們最熟悉.最直覺的那種
left-linear所畫出來的automata, 箭頭方向要相反, input state和final state要互換
rex要每個段落都逆著寫
例:
S->abS|a
我們可以寫出 (ab)*a
若是 S->Sab|a
我們則要寫出 a(ab)*
- - -
11.
13.(a)
13.(b)
沒有留言:
張貼留言