? asked in 科學數學 · 1 decade ago

regular language 的證明題

Is the following language regular?

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

Update:

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

不要純文字

3 Answers

Rating
  • 1 decade ago
    Favorite Answer

    當然不是 regular的

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

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

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

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

    Source(s):
  • 1 decade ago

    不是耶 題目就是這樣

    不過這是正規語言的

  • ?
    Lv 5
    1 decade ago

    應該是 non-regular 吧.

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

Still have questions? Get your answers by asking now.