言語が標準であるかどうかを示す

Question

次の言語の規則性を実証する必要があります。{xy∈{a、b} * | | X | _a = 2 | Y | _b}これは、xyの形の単語を参照します。この場合、inサブワードxの出現数は、サブワードyのbの出現数の2倍です。私はそれが定期的だと思うが、私はそれを示す方法を知らない。事前

Answer 1

で

おかげ言語：

{ xy in {a,b}* such that |x|a = 2|y|b } 

言語(aa)* = {e, aa, aaaa, ...}内の文字列を考えてみましょう。 Myhill-Nerode定理の区別不能な関係によって、これらの文字列のそれぞれが区別できることを示します。これは、言語のDFAには無限に多くの州、矛盾がなければならないことを意味します。

を言語に含まれない文字列に変換する最短文字列は、abです。言語に含まれていない文字列にaaが含まれる最短文字列はabbです。言語に含まれていない文字列にaaaaが含まれる最短文字列はabbbです。一般に、a^(2n)を言語に含まれない文字列に変換する最短文字列はab^(n+1)です。そのような文字列はa^(2n+1) b^(n+1)という形式になり、その言語にはaという文字列が1つもありません。 (aa)*という形式のすべての文字列は、この言語の最小文字列DFAを他のすべての文字列と異なる状態にする必要があります。

これを確認する別の方法は、クロージャのプロパティです。通常の言語は交差点で閉じています。この言語の共通語を通常の言語a(aa)*b*と置き換えてください。今度は|x|a = 2|y|bという条件は、|w|a > 2|w|bの場合にのみ、明らかに満足されます。

• |w|a > 2|w|b場合、我々はa S
• の奇数を有するので|w|a = 2|w|bが不可能な場合、2|w|bに等しい長さを有するようにxを選択します。 yには特別なaが追加されますが、これは問題ありません。
• |w|a < 2|w|bの場合、分割の左側にはbが必要ですが、aの右側に分割するたびに奇数のaが左にあるため不可能です。

この条件（b Sなどaの2倍以上とb S続いa Sの奇数）を有する言語が正規言語ではありません。これを見るには、文字列a^(2p+1) b^(p+1)と通常の言語のポンピング補題を使用して、bの数を変更せずにポンピングでaの数を減らすことができると主張することができます。