問題タブ [context-free-language]

ポンピング補題を使用して、言語が文脈自由かどうかを証明するテストが近づいています。練習問題を解こうとしているのですが、うまくいきません...

練習問題は、a)～j)について、次の言語が文脈自由かどうかを証明せよ。文脈自由であれば、それを生成する文脈自由文法を与えてください。

最初の 2 つは次のとおりです。

誰かがこれらの最初の 2 つを解決し、その方法を詳しく説明してくれれば、残り (c から j) を自分で理解できると確信しています。

私は LL(1) 解析が初めてで、現在、言語の解析テーブルを作成する方法を見つけようとしています:

と

と

次の文法を定義しています。

しばらく作業した後でも、この文法が曖昧であることを示す独特の構文木を構築するための文字列を見つけることができませんでした。のように: aaabbb、abab など。この文法は明確であるように思われました。何か助けはありますか？

次の問題の解決策を見つけたいのですが、時間の EBNF を年-月-日と月-日-年の 2 つの形式で記述して違いを確認する必要があります。

通常の順序 (02-10-1954) ではなく、年、月、日 (1954-02-10) の形式で構造化整数として日付を記述する利点を 1 つ特定してください。

形式: 年月日。これが私が思いついたものです：

年は 2099 年になり、これらのルールは機能すると思いますが、当時の EBNF を記述するより良い方法はありますか? 私は何かが恋しいですか？

問題は：

a. mpかっこが一致するすべてのシンボルを記述する名前付きの直接再帰 EBNF ルールを作成します: ()、()()()、()(()())、および((())())(()(()))()。(、())(、または(()()を正当なものとして認識すべきではありません。
b. 表形式の証明とその派生ツリーを記述し()(()())て、合法であるとどのように認識されているかを示します。

これまでのところ、1 つのもっともらしい解決策を考えてきました。それが正しいかどうか、または何かが欠けているかどうかはわかりません。

助言がありますか？

次の言語をご覧ください。

(a, b, c)* − {anbncn|n≥0}

私の質問は次のとおりです。文脈自由文法をどのように書くのですか?

一般に、何かが除外されている (つまり、"-" 記号がある) 場合、どうすれば文法を記述できますか?

文脈自由文法なので、

S --> aSbS|b|epsilon

受け入れられた言語をどのように説明できますか?

ある程度の長さの言語を見つけることはできますが、説明することはできません。