2つの言語の共通点は何ですか？

Question

は、私はL1が正規言語であるとL2はPDAで表すことができることを知っている言語

L1={anb2m|n,m≥1} 
L2={anb3n|n≥0} 

L = L1 ∩ L2 

を考えます。

しかし、私はLが{a2nb6n|n≥1}であるという答えを理解していません。このソリューションはどのように計算されましたか？

Answer 1

言語は単なる（有効な文字列の）セットなので、ここでは整数演算では単なる単純な問題です。問題の本質に到達するためには、正式な言語のエレガントな衣装を取り除くことだけが必要です。

L1とL2の両方のセットは{acount(a)bcount(b)|j,k≥0}のサブセットです。すなわち、いくつかの番号asと、その後にいくつかの番号bsが続きます。 の条件では、m≥1の場合は2mである必要があるため、count(b)は正の偶数に制限されます。 L2の条件は、count(b)が正確に3×count(a)であることを制限します。

ここで、述語で定義された2つの集合の共通部分は、両方の述語が真となるような要素の集合です。したがって、count(b)は、2と3で割り切れる必要があります。つまり、6で割り切れる必要があります。換言すれば、ある正の整数nに対しては6nでなければならない。つまり、count(a)は、bのちょうど3倍多くあるので、2nでなければなりません。それはあなたに答えを提供します。

L2と同様に、Lは規則的ではありませんが、非常によく似たPDAで実装できます。