4

特定の言語が通常か、文脈自由か、文脈自由でないかを判断するのに助けが必要です。答えには簡単で非公式な説明で十分なので、ポンピング補題を使用する必要はありません。

私が次の言語を持っているとしましょう：

L1 = { w ∈ {a, b, c, d}* | #a(w) is even, #b(w) = 1 mod 3, w does not have 
                           a substring abc }

L2 = { w  ∈ {a, b, c, d}* | #a(w) is even, #b(w) < #c(w) }

L3 = { w  ∈ {a, b, c, d}* | #a(w) < #b(w) < #c(w) }

これが私の解決策です：

L1 = L2 ∩ L3 ∩ L4 where

L2 = #a(w) is even
L3 = #b(w) = 1 mod 3
L4 = w does not have a substring abc

L2 は無限のメモリを必要としないため、L2 用に DFA を構築できます。したがって、L2 は規則​​的です。L3 については、上記と同じ理由です。L4 の場合、単純に「abc」を受け​​入れないため、通常の DFA を構築できます。

正規言語は ∩ の下で閉じているため、L1 は正規です。

L2 の場合、言語を次のように分割できます。

L2 = L3 ∩ L4 where

L3 = #a(w) is even
L4 = #b(w) < #c(w)

L3 に対して DFA を構築できることがわかっているため、L3 は正則です。L4 はコンテキストフリーです。スタックを使用して a:s と b:s の数をカウントする PDA を構築できるからです。

正規言語と文脈自由言語の ∩ が文脈自由言語になるため、L2 は文脈自由です。

L3 の場合、スタックが 1 つに制限されているため、コンテキストフリーではないことがわかります。2 つ以上の比較を行うには、より多くのスタックが必要です。

私の推論は正しいですか？もうすぐ試験があり、この背後にあるアイデアが得られたかどうかを知る必要があります.

前もって感謝します

4

1 に答える 1

3

はい、3 つのすべての点で正しいです。L1 は通常、L2 は文脈自由、L3 は文脈自由ではありません。L1 と L2 のクロージャ プロパティを正しく適用し、最後のものについての推論は多かれ少なかれ正しいです。最後のルールについては、そのルールを使用しないように警告します...言語を認識する方法について考える方法は複数ある可能性があり、その中にはスタック以上のものを必要とするものもあれば、スタックを必要としないものもあります. たとえば、非文脈自由言語 L = {a^nb^nc^n} を考えてみましょう。この言語の補完は文脈に依存しませんが、使用する規則をずさんに適用すると、別のことを信じるようになる可能性があります (問題を適切に検討するまで)。

于 2013-01-03T17:08:37.920 に答える