問題タブ [pumping-lemma]

コンパイラに関する質問があります。

{(ab)^n | n >= 0} は正規言語ですか?

しかし、私はその NFA を描くことができます。しかし、ポンピング補題を使用すると、矛盾した答えが得られます。

誰でも私を助けることができますか？

L = {a^f(m) | m >= 1 }がf: Z^+ -> Z^+単調に増加し、その中のすべての要素nがそのようなものZ^+にm属していることに準拠しているとしましょう。Z^+f(m+1) - f(m) >= n

L が正規言語であることを証明することは可能ですか?

ポンピング補題を使用して、次の言語が規則的でないことを証明しようとしています

L={ a^ib^j | i^2 > j}

これに関するヒントはありますか？私は完全に立ち往生しています。

ありがとう。

私は文脈依存の補題をポンピングすることをグーグルで調べました、そしてそれは文脈自由言語の結果だけを生み出すようです。

補題をポンピングすることは、言語が文脈自由のみであることを証明することだけを可能にしますか？コンテキストに依存しませんか？

どのようにアイデアはありますか？

私は自分のテストでこの質問を間違え、誰かがそれを説明できるかどうか疑問に思っていました。そして、結論に達するためにとられたステップを示しました。どんな助けでもいただければ幸いです。

L_neq = {0 ^ i1 ^j|のPL証明で i <j} m状態のDFAが与えられた場合、誰かが文字列0 ^（m / 2）1 ^（m / 2 + 1）を選択します。次に、y = 0を選択し、ポンピングすることで、L_neqの外側にある文字列0 ^（m / 2 + 1）1 ^（m / 2 + 1）に到達できることを示します。この証明は正しいですか？なぜまたはなぜそうではないのですか？

さらに、この証明が間違っている場合は、正しい証明を書き留めてください。

ありがとう

私はこれについてかなり長い間考えていますが、それでもそれについては遠くまで行くことができませんでした。最初のステップは、形式o ^ Mの言語を考えると簡単です。ここで、Mは、対戦相手が与えたものよりも大きい素数です（たとえばn）。ここから、対戦相手がどのようであっても、どのように証明できるかわかりません。文字列を壊して、文脈自由言語（したがって正規言語）のクラスに属していないことを示すために、いつでもそれをポンピングできます。

PS：宿題の質問ではありません。私はすでにこのコースを完了しています。コース期間中に解決できなかったので、解決しようとしています。

言語 L は、正規言語のポンピング補題と、文脈自由言語のポンピング補題を満たします。L に関する次の記述のうち、正しいものはどれですか?

A. L は必然的に正規言語です。

B. L は必然的に CFL ですが、レギュラーではありません。

C.Lは必然的に非正規です。

D.なし

疑問に思っているところを明確にします。L が正規言語のポンピング補題を満たす場合、それは必ずしも正規ではありません。文脈自由と同じ。したがって、レギュラーでも非レギュラーでもかまいません。CFL または非 CFL。与えられた答えは B ですが、私の意見では D であるべきです。

正規言語のポンピング補題を使用して、言語が正規かどうかを調べます。宿題に、ポンピング補題を言語に適用する方法がわからないという質問があります。

$ は、a と b を分割するための単なる定数です。

次のような言語もあります。

a と b を分割するものは何もなく、a のゼロの数と b の 1 の数について仮定することはできないことを理解していますよね？それとも私は間違っていますか？

これらの言語にポンピング補題を適用して、正規かどうかを証明するにはどうすればよいでしょうか?

私は完全に立ち往生しているポンピングレンマの質問があります...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

それはCFLですか？

これらの条件をすべて記憶するには、1 つのスタックだけでは十分ではないため、CFL ではないと考えています。na (w) < nb (w) または na (w)< nc (w),nb (w) < nc (w) であることを思い出すことができますが、na (w) < nb (w) < nc (w) ではありません。さらに、言語が a^pb^2pc^3p の場合と、|vy| の場合よりも p 回 L は CF ではありませんが、p 回ポンプアップすることは可能ですか?

または解決策のアイデアはありますか？

次の言語は文脈自由ですか?

これを生成するために文脈自由文法を考え出そうとしましたが、できないので、文脈自由ではないと仮定しています。矛盾による私の証明については：

L が文脈自由であると仮定すると、

ポンピング補題によって与えられる定数を p とします。

文字列 S = a^pb^pc^pd^p を選択します。ここで、S = uvwxy

|vwx|として <= p の場合、最大で vwx に 2 つの異なるシンボルを含めることができます。

ケース a) vwx には 1 つのタイプのシンボルのみが含まれているため、uv^2wx^2y は i+s != k+r になります。

ケース b) vwx には 2 種類のシンボルが含まれています。

i) vwx は b と c で構成されているため、uv^2wx^2y は i+s != k+r になります。

ここで私の問題は、vwx が a と b、または c と d のいずれかで構成されている場合、i と k または s と r が一斉に増加して i+s == k になる可能性があるため、それらをポンピングしても言語が壊れる必要はないということです。 +r。

私は何か間違ったことをしていますか、それともこれは文脈自由言語ですか?