Automata-theory-pumping-lemma-for-regular-grammar

通常の文法のポンピング補題

定理

Lを通常の言語にします。 次に、 L のすべての文字列 w のような定数 ’c’ が存在します-

*| w | ≥c*

*w* を3つの文字列 *w = xyz* に分割できます。

• | y | > 0
• | xy | ≤c
• すべてのk≥0について、文字列xy ^ k ^ zもLにあります。

ポンピング補題の応用

ポンピング補題は、特定の言語が規則的でないことを示すために適用されます。 言語が規則的であることを示すために決して使用すべきではありません。

• L が規則的な場合、Pumping Lemmaを満たします。
• L がPumping Lemmaを満たさない場合、それは非正規です。

言語Lが正規でないことを証明する方法

• 最初に、 L が規則的であると仮定する必要があります。
• したがって、ポンピング補題は L を保持する必要があります。
• 矛盾を得るためにポンピング補題を使用します-
• * | w |のように w を選択します≥c *
• * | y |のように y を選択します≥1 *
• * | xy |のように x を選択します≤c *
• 残りの文字列を* z。*に割り当てます
• 結果の文字列が L. に含まれないように k を選択します

したがって、Lは規則的ではありません。

問題

*L = \ {a ^ i ^ b ^ i ^ | i≥0}* は規則的ではありません。

*_ソリューション_* -

• 最初に、 L は規則的であり、nは状態の数であると仮定します。
• w = _a ^ n ^ b ^ n ^ _としましょう。 したがって| w | = 2n≥n。
• 補題をポンピングすることにより、w = xyzとする（| xy | ≤n。
• x = a ^ p ^、y = a ^ q ^、およびz = a ^ r ^ b ^ n ^とします。ここで、p + q + r = n、p≠0、q≠0、r≠0です。 したがって| y | ≠0。
• k = 2とします。 次に、xy ^ 2 ^ z = a ^ p ^ a ^ 2q ^ a ^ r ^ b ^ n ^。
• as =（p + 2q + r）=（p + q + r）+ q = n + qの数
• したがって、xy ^ 2 ^ z = a ^ n + q ^ b ^ n ^。 q≠0であるため、xy ^ 2 ^ zはa ^ n ^ b ^ n ^の形式ではありません。
• したがって、xy ^ 2 ^ zはLにありません。 したがって、Lは規則的ではありません。