nlp - (a^p)(b^q) は通常の言語ですか

Question

{(a^p)(b^q):p,Q は N に属する} は通常の言語であるとどこかで読みました。しかし、私はこれが正しいとは思わない。これは、ポンピング補題を使用して証明できます。私のソリューションが正しいかどうかを確認したいだけです

y を ab とする。したがって、n>=1 の場合、a の前に b がいくつかあるため、x(y^n)z は L に属しません。しかし、表現はこれを許しません。したがって、(a^p)(b^q) は RL ではありません

score 7 · Accepted Answer

ポンピング補題を使ったのは少し前のことですが、a ^p b ^qは間違いなく正規言語です。正規表現を書くのも簡単です! a * b *

ただし、似たようなa ^p b ^pは規則的ではありません。bシンボルを消費し始めるとき、消費した aシンボルの数を覚えておく必要があり、有限オートマトンは任意の数を「覚える」ことができないからです。あなたの場合、これは問題ではありません。

score 0 · Accepted Answer

ポンピング補題は次のように述べています。言語Aが通常の場合=>数値p（ポンピング長）があります。ここで、sがL内の|s|のような任意の文字列である場合 > = pの場合、sは次の条件を満たす3つの部分s=xyzに分割できます。

特定の言語Lが規則的でないことを示す正しい方法は、Lが規則的であると想定し、矛盾に到達しようとすることです。

あなたの言語が規則的ではないと仮定しようとするなら、あなたは最初に言語の不規則性を表す種類の文字列を検索するべきです。ⁿ > =0の場合に^pbnを試してみましょう。

この文字列に対していくつかの仮定を行うことができます。|xy| <= pであるため、yはaのみで構成されていることがわかります。この時点で、何度でもポンピングできますが、xyizはすべてのⁱ >=0の言語のメンバーです。

^同様に、ⁿ >=0の場合にnbpを選択しても、矛盾は発生しません。

L = {a ⁿ b ⁿ | n> = 0}は規則的ではありませんが、pとqに制約はありません（つまり、aとbの両方の出現をカウントする必要はありません）。

ただし、正規表現で表現できる場合に限り、言語は正規です。そしてこの場合、あなたはそれをすることができます：a *b*。したがって、この言語は正規言語であると結論付けることができます。

編集：p <= qの場合、言語は規則的ではありませんが、pとqを検討しています。

2 に答える 2