? 發問時間: 科學數學 · 1 0 年前

regular language 的證明題

Is the following language regular?

L = {w1cw2 : w1, w2 ∈ {a, b}*, w1 ≠ w2}.

已更新項目:

希望能用一些數學的方式證明出

不要純文字

3 個解答

評分
  • 1 0 年前
    最佳解答

    當然不是 regular的

    regular language 表示可以用一個 finite state machine認出這個pattern

    但是這個language 必須要記住 infinite 長的 w1, 才能跟w2比對看看是否一樣. 所以不可能靠finite state machine來達成.

    2008-04-27 20:21:50 補充:

    這證明要用課本中其他已知的not regular language來推倒, 我不知道你課本中有哪些已知的例子, 沒辦法幫你

    參考資料:
    • 登入以對解答發表意見
  • 1 0 年前

    不是耶 題目就是這樣

    不過這是正規語言的

    • 登入以對解答發表意見
  • ?
    Lv 5
    1 0 年前

    應該是 non-regular 吧.

    要記錄 w1 與 w2 並比較相異性, 也許要用 turning machine. 但理由忘光了... 自動機課本裡應該有...

    • 登入以對解答發表意見
還有問題?馬上發問,尋求解答。