問題タブ [context-free-language]

L= {a^ib^ic^i : i >= 1} の補数が文脈自由であることを証明しようとしています。L の補数は次のとおりです: {w は {a,b,c} 上の単語です* : w は L にありません}。

私たちが知っているように、文脈自由言語は和集合の下で閉じられています。だから、私は自分の言語 ({a^ib^ic^i} の補数) を文脈自由サブセットに分割しようとしています。サブセットを見つけるのを手伝ってくれる人はいますか? 私がしようとするたびに、私はL *で終わります！

ありがとうございました。

私の教授は、与えられた言語が規則的か、文脈自由だが規則的ではないか、または文脈自由でないか (つまり、PDA を描画したり、文脈自由文法を書いたり、文脈にポンピング補題を使用したりすることなく) を迅速に判断することを期待しています。 -無料の言語)。

通常の言語が何であるかを一目ですばやく判断するのに役立つヒントは知っていますが、言語が文脈自由であるかどうかはわかりません。

ありがとうございました。

こんにちは、私は次のCFGを持っています

イプシロンを削除して、次の結果になりました。

単位規則を削除しようとしているところで、すべての非端末が次のような同じ結果になりました。

私の質問は、私のイプシロンの除去は正しいですか? とにかくそれをすることはありますか？

Formal Languages と Automata Theory を勉強していますが、本の中で答えられていない問題について質問があります。質問は：

この言語はコンテキストフリー、レギュラー、またはコンテキストセンシティブですか?

L={a^ib^jc^k|i<=j または j<=i , j=k}