Research Space for Linear Algebra & Discrete Mathematics
1, 2: 如定義所述, type 0沒有限制, type 1是限制字串長度一定要越推越長, type 2是限制只能從一個nonterminal開始推, type 3限制最多, 規定推出來的部分一定要有terminal, 至於那些名字, 可以不用太在意它, 中文不太重要, 只要知道我們一般會稱type 3為regular language, type 2為context-free language, 還有稱type 1為context-sensitive即可, 畢竟這些真的要研究可以講一門課, 也就是一般學校裡開的正規語言, 自動機或計算理論, 在那些課裡我們才能比較深入的研究那些語言的性質, 在離散裡面通常只會稍微點一下它的定義3. AB是子串的串連, 然而若是先將 A 和 B 分開來看, 不管是取聯集或者是取Kleene closure, 其實效果常常都會差滿多的, 也因此如果是false, 簡單的取A = {0}, B = {1}, 通常都可以找到這類題目的反例, 因為像是01這種有0又有一的字串, 只會出現在串連的時候, 另外有時稍微判斷一下長度, 也可以幫助找反例4. 這種題目的確不太好做, 因為很容易漏考慮, 想法大致上是想辦法分類記錄所有可能出現的狀態(以這題為例就是S, A, B這三種狀態), 可以遞迴去想規則, 並且每個狀態都能夠導出會被接受的字串
張貼留言
1 則留言:
1, 2: 如定義所述, type 0沒有限制, type 1是限制字串長度一定要越推越長, type 2是限制只能從一個nonterminal開始推, type 3限制最多, 規定推出來的部分一定要有terminal, 至於那些名字, 可以不用太在意它, 中文不太重要, 只要知道我們一般會稱type 3為regular language, type 2為context-free language, 還有稱type 1為context-sensitive即可, 畢竟這些真的要研究可以講一門課, 也就是一般學校裡開的正規語言, 自動機或計算理論, 在那些課裡我們才能比較深入的研究那些語言的性質, 在離散裡面通常只會稍微點一下它的定義
3. AB是子串的串連, 然而若是先將 A 和 B 分開來看, 不管是取聯集或者是取Kleene closure, 其實效果常常都會差滿多的, 也因此如果是false, 簡單的取A = {0}, B = {1}, 通常都可以找到這類題目的反例, 因為像是01這種有0又有一的字串, 只會出現在串連的時候, 另外有時稍微判斷一下長度, 也可以幫助找反例
4. 這種題目的確不太好做, 因為很容易漏考慮, 想法大致上是想辦法分類記錄所有可能出現的狀態(以這題為例就是S, A, B這三種狀態), 可以遞迴去想規則, 並且每個狀態都能夠導出會被接受的字串
張貼留言