1

1 つの問題を解決しようとしていますが、1 つの問題を解決するためのヒントが緊急に必要です。

以下の言語が文脈自由であることを示すために、union の下でクロージャーを使用します。

{a m b n c p d q : n=q または m <= p または m+n=p+q }

4

1 に答える 1

4

問題が何であるかを特定していないので、知っておく必要があることだけを説明します。

労働組合の下で閉鎖- とはどういう意味ですか?
言語Lと言語Sがあり、両方が文脈自由である場合、言語の結合も文脈自由であることがわかります。

L ∪ S = 文脈自由言語

CFL のクロージャー プロパティの詳細については、こちらを参照してください。興味がある場合は、Web 上でこれの証明を見つけることができます (または、独自の証明を作成することもできます)。

これをどのように使用して問題を解決できますか?
この言語仕様があります ( と呼びましょうL):

L = {a m b n c p d q : n=q または m <= p または m+n=p+q }

この言語を他の 3 つの言語に分割できます。

A = {a m b n c p d q : n = q }
B = {a m b n c p d q : m <= p }
C = {a m b n c p d q : m+n = p +q }

それは簡単にわかりますA ∪ B ∪ C = L。

A、B、C が文脈自由であることを証明できれば、L も文脈自由であると結論付けることができます。

解決策
言語が文脈自由かどうかを判断するには、この回答を参照してください。答えを引用するには：

まず、主語で言語を形成する文脈自由文法の構築を試みる必要があります。すべての生成の左側に非終端記号が 1 つだけ含まれている場合、文法は文脈自由です。定義上、存在する場合、その言語は文脈自由です。

同等のコンストラクトは、プッシュダウン オートマトンです。DFA と同じですが、スタックが利用可能です。文法よりも構築が簡単かもしれません。

したがって、言語 A、B、C のそれぞれについて CFG (または PDA) を作成できれば、問題は解決したことになります。

言語を見てみましょう: s とsを同量持たなければならないA形式の文字列を生成する文法が必要です。a..b..c..d..bd

S -> AE
A -> Aa  | ε
E -> bEd | C
C -> Cc  | ε

Sは開始変数 (または非終端記号) でεあり、空の文字列です (null 記号を使用する人もいます^が、私は常に を使用するように言われてきましたε)。この文法は言語を生成できるはずでAあり、したがってA文脈自由です。(誰かがエラーを検出した場合はお知らせください。しばらく CFG を作成していません)。

これは演習なので、残りの部分はあなたに解かせますが、やり方は分かっているはずです。

于 2013-04-29T16:52:54.200 に答える