私は宿題のためにこの練習をしています：
言語 L があるとします。その言語
pref(L)(すべてLの単語を含むのすべての接頭辞L) は通常の言語であることがわかっています。Lこれは、言語も規則的であることを意味しますか?
の NFA を取り、pref(L)それを ( からの 2 つのイプシロン遷移を介してq0) 2 つの別個の NFA に分割Lしpref(L)\Lました。
私が実際に得たのは の NFA でL、これは正規であることを意味します。
これがその方法なのか、合法なのかはわかりません。別のリードをいただければ幸いです。
前もって感謝します、
ヤロン。
pref(L) が正則である場合、L も正則であるとは限りません。
例として、Σ = {a} を単項アルファベットとします。L が Σ 上の任意の無限言語である場合、pref(L) = Σ*であると主張します。これを確認するには、すべての pref(L) が Σ 上の言語であるため、最初に pref(L) ⊆ Σ* であることに注意してください。ここで、a nの形式を持たなければならない Σ* の任意の文字列を考えます。L が Σ 上の無限言語である場合、m ≥ n であるa mの形式の文字列を少なくとも 1 つ含まなければなりません。その場合、a nは a mの接頭辞になるため、a n ∈ pref(L) になります。これは、Σ* ⊆ pref(L) と pref(L) ⊆ Σ* を示しているため、この場合は Σ* = pref(L) です。
あとは、Σ = {a} 上の非正規言語を見つけるだけです。例として、言語 { a 2 n | 長さが 2 のべき乗であるすべての文字列の n ∈ N }。Myhill-Nerode 定理またはポンピング補題のいずれかを使用して、この言語が規則的でないことを証明することができます。しかし、上記の結果から、pref(L) が正規言語であることがわかります。
お役に立てれば！