Compiler作業參考(1) B班

101年度第2學期 期中考前



[HW01]
根據課本的grammar照著畫，應該沒什麼問題。

[HW02]

1. For the following description, write a regular expression, NFA and DFA.
a. String with alphabet {a,b,c} that have odd number (1,3,5,7...) of 'a'(s).

     (b|c)* a (b|c)* ( a (b|c)* a (b|c)* )*   ...至少產生一個a 之後就兩兩一起產生
b. String with alphabet {a,b,c} that first 'b' occurs before first 'a'.
    c* b (b|c)* a (a|b|c)* ...一開始可以有任意數量的c，出現第一個b後，可以有b和c的任意組合，直到出現a後，可以開始出現 a b c 的任意組合

c. Binary number {0,1} that mod 4 equals 0. 

    0 | ( 1 (0|1)* 00 )  ...0或者是四的倍數，mod 4都是0
d. String with alphabet {a,b} that doesn't consists sub string "aba".

   上課有講過...答案會很長，先畫一個FA出來會再反堆regular expression會比較簡單

2. Explain why the string, a...ab...b, same number of a and b, can't be express as regular expression.

  因為以FA表示的話，這樣的字串，需要有與a的數量成正比的state數目來紀錄a的數量。在a的數目沒有限制的情況下沒辦法用有限個狀態表示此字串。所以這種字串無法表示成FA/regular expression。

3. Draw a NPDA that accepts string like "a...ab...b", more 'b's than 'a's.

  這個上課也講過，算是補充，考試不會考。

*可以參考先前的lecture note

[HW03]

1. Construct a CFG for language with alphabets, {a,b}, which is a palindrome (same string with backward, ex: abbabbabba).

 S-> aSa | bSb | (lambda)   ...對稱產生就對了

2. Show that the following CFG is ambiguous.

 

S -> A

A -> AaA | B

B -> bcb | cbc

某些情況下同一字串可產生兩種tree

如bcbacbcacbc

 

3. Rewrite the CFG above, make it *right-most derivation* only, so that it is no longer ambiguos.

S  -> B

B -> bcbA | cbcA | bcb | cbc

A -> aB