Research Space for Linear Algebra & Discrete Mathematics
1. (a)不是regular, 上課有證過, 另外, 我們可以很容易造出context-free grammar導出它, S -> aSb|ab, 所以它是context-free(b)它顯然也不是regular, 不過這個要稍微記一下囉, 它是context-sensitive(c)這個應該很容易造出regular grammar導出它, 所以它是regular2. 這個是考古題, 書上有, 您可以參考書上P8-41其實就是把{A, D, E}當一堆, {B, C, F, G}當一堆, 找出第一堆指向第二堆的所有邊的capacity總和
請問要怎麼區分這些context-sensitivecontext-free,regular?有比較容易分辨的方式嗎?書上的不是很好了解..感謝了
(b)for (a=l; a<=n; a*=2)for (b=l; b<=a; b++)C++;(c)for (a=l; a<=n; a*=2)for (b=l; b<=a; b*=2)C++;可以麻煩老師解一下這兩題的複雜度嗎?
就按書上的定義去想, 如果能夠production rule左邊都只放一個nonterminal, 那就是context-free不過L3可以不用寫grammar, L3 = b*abb*, 它可以寫成regular expression, 所以它是regular grammar
請問第一題這種該如何判斷呢?
1.
回覆刪除(a)不是regular, 上課有證過, 另外, 我們可以很容易造出context-free grammar導出它, S -> aSb|ab, 所以它是context-free
(b)它顯然也不是regular, 不過這個要稍微記一下囉, 它是context-sensitive
(c)這個應該很容易造出regular grammar導出它, 所以它是regular
2. 這個是考古題, 書上有, 您可以參考書上P8-41
其實就是把{A, D, E}當一堆, {B, C, F, G}當一堆, 找出第一堆指向第二堆的所有邊的capacity總和
請問要怎麼區分這些context-sensitive
回覆刪除context-free,regular?
有比較容易分辨的方式嗎?
書上的不是很好了解..
感謝了
(b)for (a=l; a<=n; a*=2)
回覆刪除for (b=l; b<=a; b++)
C++;
(c)for (a=l; a<=n; a*=2)
for (b=l; b<=a; b*=2)
C++;
可以麻煩老師解一下這兩題的複雜度嗎?
就按書上的定義去想, 如果能夠production rule左邊都只放一個nonterminal, 那就是context-free
回覆刪除不過L3可以不用寫grammar,
L3 = b*abb*, 它可以寫成regular expression, 所以它是regular grammar