問題タブ [formal-languages]

次の言語を認識するPDAを作成します：bよりも多くのaを含む文字列の言語

私はこの質問に数日間苦労してきました、私は完全な精神的ブロックにぶつかったようです。この問題をどのように解決できるかについて、誰かがガイダンスや指示を提供できるでしょうか？

文脈自由言語のコレクションの和集合は常に文脈自由ですか？あなたの答えを正当化してください.....

答えがイエスであることは知っていますが、どうすればそれを証明できますか？

ほとんどが文脈自由言語でコーディングしている場合、チューリングマシン（帰納的可算言語を受け入れる）の出力をどのようにシミュレートできるかを本当に理解できません。

誰かが次の質問で私を助けてくれることを望んでいました.答えが最善ですが、正しい方向に私を向けることができれば. 私は大学の最終学年の学生で、これらの質問は形式的方法に関する以前の試験からのものであり、今年の論文の準備ができている答えを知っていればできます。私たちの講師は最高ではないようで、これについて多くをカバーしていないため、正確な答えを見つけることは不可能であることが証明されています. グーグルはあまり役に立ちませんでしたし、推奨された本もありませんでした.

1 - ∃x • P (x) が ¬∀x • ¬P (x) と論理的に等価であり、∀x ∈ S • P (x) が ∀x • x ∈ S ⇒ P (x) を意味すると仮定すると、 ∃x ∈ S • P (x) は、∃x • x ∈ S ∧ P (x) を意味します。

2 - 定義を示すために証明する必要がある 2 つのステートメントを説明してください。

仕様の正しい実装です:

L={w|#a(w)=#b(w)=#c(w)}クロージャーを使用して言語が文脈自由ではないことをどのように証明できますか?

ありがとう

編集 ：

私はその言語L1 = {a^i b^i c^i | i>=0}が文脈自由言語ではないことを知っています。今、私は別の言語を見つけようとしていますがL2、どこが正規言語L2であるかを矛盾させるために探しています。L1L2L1∩L2

ポンピング補題を使用してコンテキストフリーではないことを証明しようとしてL={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }いますが、それができないようです。もしも

次に、とのvxy両方、または のみまたは のみのいずれかです。abba

それを示すためにどのようにポンピングできますか？

L={a^nb^nc^n} が与えられた場合、生産規則を見ずに、この言語が規則的でないとどうすれば直接言えますか? 私はポンピング補題を使うことができますが、文法を見ただけでこれは正規のものではないと言っている人もいます。どのように可能ですか？

ここで、SO の人々は時々、「X は正規表現ではないため、X を正規表現で解析することはできません」のようなことを言います。しかし、私の理解では、最新の正規表現エンジンは、チョムスキーの意味で正規言語以上のものと一致させることができます。私の質問:

サポートする正規表現エンジンが与えられた場合

• 後方参照
• 無制限の幅のルックアラウンド アサーション
• のような再帰(?R)

どのような言語を解析できますか? 文脈自由言語を解析できますか?そうでない場合、反例は何でしょうか?

(正確には、「解析」とは、「文法 X によって生成されたすべての文字列を受け入れ、他のすべての文字列を拒否する単一の正規表現を構築する」ことを意味します)。

追加: 私は、最新の正規表現エンジン (Perl、Net、Python 正規表現モジュール) が解析できないコンテキストフリー言語の例を見ることに特に興味があります。

私はすでに遭遇したトークンのセットを含む環境を持っています。新しいトークンを見るとき、そのトークンを現在の環境に追加したいと思います。基本的には、構文解析を実行する環境での集合和集合演算を表現したいと思います。

Γ'={Γ、x}のようなもの

変数'x'を削除したい場合（環境からxを削除します）

x∈Γの場合、Γ'=Γ--x。

これらの2つの形式を書くための適切な方法は何ですか。ありがとう。

私が を持っている場合Σ={a}、 が を持っている単語は何Σ*ですか?

Σ*= {a,aa,aaa,aaaa.....}?

ありがとう