2CFLの交差点

セット $A$ アルファベットのすべての文字列が含まれています $\{a,b,c\}$ で始まります $a$、で終わる $c$ と同じ数で $b$砂 $c$s。同様に、$B$ 同じアルファベットの文字列で始まり、 $a$、で終わる $c$ と同じ数で $a$砂 $b$s。

だから交差点 $A\cap B$ 単にアルファベットのすべての文字列を含む $\{a,b,c\}$ で始まります $a$、で終わる $c$、同じ数の $b$砂 $c$sと同じ数の $a$砂 $b$s。平等の推移性によって（つまり、$x=y$ そして $y=z$ その後 $x=z$、 どこ $x$、 $y$ そして $z$ の数です $b$s、 $c$砂 $a$文字列内のs）、次のように言うことで、これらの最後の2つの条件を表すことができます。 $a$s、 $b$砂 $c$sは同じです。つまり、$A\cap B$ の形です $a^n b^n c^n$ いくつかの自然数のために $n$ （もちろんここでは文字を使用できます $m$、またはその他の任意の文字の代わりに $n$）。

あなたはそれを持っています $A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$ そして $B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$。場合$w\in A$、それからあります $r,s\in\mathbb{N}$ そのような $w=a^rb^sc^s$。それもあれば$w\in B$ （そのような $w\in A\cap B$）、次にあります $t,u\in\mathbb{N}$ そのような $w=a^tb^tc^u$。

したがって、 $a^rb^sc^s=w=a^tb^tc^u$。

私たちはそれを仮定する必要があります $a,b,c$別の文字です。そうでなければ、求められている結論は満たされません。たとえば、$a=b=c$、その後 $A=B=\{a^n:\ n\in\mathbb{N}\}$、ながら $A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$。この仮定は、明示的に述べられていない場合、おそらく意図されたものです。

さて、 $r<t$ （または $r>t$）、次に比較します $(r+1)$-ソー $(t+1)$-th）の手紙 $a^rb^sc^s$ そして $a^tb^tc^u$ 私たちは得るだろう $a=b$。これは矛盾です。したがって、$r=t$。

そう、 $a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$。同じ分析を$r$ そして $s$。場合$r<s$ （または $r>s$）比較します $(r+1)$-ソー $(s+1)$-th）の文字 $a^rb^sc^s$ そして $a^rb^rc^u$。これはそれを与えます$b=c$、これは矛盾です。したがって、$r=s$。

そう、 $a^rb^rc^r=w$。