E = {a, b} とします。L0 = {(b^(n))(a^(2n)) : n >= 0} とします。L = ((NOT OPERATION)L0) とする
L は規則的ですか、文脈自由ですが規則的ではありませんか、それとも文脈自由ではありませんか? あなたの答えを証明してください。
私は L が何であるか、そして L0 が質問でどのように説明されたかと同様の方法でそれを説明する方法と、答えを探しています。
説明は私にとって非常に重要です。貢献したい場合は、具体的にお願いします。テストのためにこの資料を理解しようとしています。
どうもありがとう！
素人の言葉を使って説明し、形式化するためのヒントを紹介します。
LE={a,b}言語にないアルファベットのすべての文字列を持つL0
言語です。これは正規の言語ではありません。
の文字L列は、L0 の DFA の非最終状態で終了するすべての文字列です。ただし、L0 用の DFA/NFA を構築できないため、L 用の DFA も作成できません。
理由: L01 つのバインドされていない数値 n では、すべての b を調べた後に格納する必要があり、a のチェック中にそれを使用する必要がありますが、DFA にはメモリがありません。上記の言語の正規表現は記述できません。
ポンピング補題 L の使用は文脈自由言語ではない
S=abは L の文字列 PL を使用して 5 つの部分に分割します
S=uvxyz
u="" v=a x="" y=b z=""
新しいn=0
文字列はS(n=0)="" which is not in Lです。
ab を で割ると
u="" v="" x=a y=b z=""
今のところn=2 S(n=2)=abb which is not in L
したがって、L は CFG ではありません。
PS: m に穴が見つかったら教えてください
ポンピングレマを学んだかどうかはわかりません。しかし、それは言語が規則的かどうかを判断する方法です。また、L0 dfa の最終統計と初期統計を交換することで L1 の dfa を作成できるため、L0 が正規の場合、L1 も正規であることに注意してください。
b^ma^2m の L0 の例を考えてみましょう。この文字列は、lema をポンピングするのに十分な大きさです。
例を xyz の 3 つの部分に分割します。
ここで |xy| < m (部分文字列 xy の要素数) および |y| >= 1。
チャンク xy < m であるため、b^m 個の b があるため、すべて b でなければなりません。
今度は y を 0 回ポンプします。
xy^0 z は、言語が bbbaaaaaa で |y|=1 の場合、言語は bbaaaaaa になり、b^na^3n に従うことを意味します。これは正規表現ではありません。
L1 が正規表現ではないことを意味します 2.