2 CFL'nin kesişimi

Set $A$ alfabedeki tüm dizeleri yazıyor $\{a,b,c\}$ ile başlayarak $a$, ile bitmek $c$ ve aynı sayıda $b$s ve $c$s. Benzer şekilde,$B$ aynı alfabedeki dizelerle yapılır. $a$, ile bitmek $c$ ve aynı sayıda $a$s ve $b$s.

Yani kavşak $A\cap B$ alfabedeki tüm dizeleri basitçe basar $\{a,b,c\}$ ile başlayarak $a$, ile bitmek $c$aynı sayıda $b$s ve $c$s ve aynı sayıda $a$s ve $b$s. Eşitliğin geçişkenliği ile (yani eğer$x=y$ ve $y=z$ sonra $x=z$, nerede $x$, $y$ ve $z$ sayıları $b$s, $c$s ve $a$s bir dizede), bu son iki koşulu sayısının $a$s, $b$s ve $c$s aynıdır, yani içindeki dizeler$A\cap B$ formda $a^n b^n c^n$ bazı doğal sayılar için $n$ (elbette burada mektubu kullanabilirsiniz $m$veya yerine tercih ettiğiniz başka bir harf $n$).

Sende var $A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$ ve $B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. Eğer$w\in A$, o zaman var $r,s\in\mathbb{N}$ öyle ki $w=a^rb^sc^s$. Eğer bizde de varsa$w\in B$ (öyle ki $w\in A\cap B$), o zaman var $t,u\in\mathbb{N}$ öyle ki $w=a^tb^tc^u$.

Bu nedenle, $a^rb^sc^s=w=a^tb^tc^u$.

Bunu varsaymalıyız $a,b,c$farklı karakterlerdir. Aksi takdirde istenen sonuç tatmin edilmez. Örneğin, eğer$a=b=c$, sonra $A=B=\{a^n:\ n\in\mathbb{N}\}$, süre $A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Bu varsayım, açıkça söylenmemişse, muhtemelen kasıtlıydı.

Şimdi eğer $r<t$ (veya $r>t$), ardından karşılaştırarak $(r+1)$-th (veya $(t+1)$-th) harfleri $a^rb^sc^s$ ve $a^tb^tc^u$ alırdık $a=b$. Bu bir çelişkidir. Bu nedenle,$r=t$.

Yani, $a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. Aynı analizi şununla yapıyoruz:$r$ ve $s$. Eğer$r<s$ (veya $r>s$) karşılaştırırız $(r+1)$-th (veya $(s+1)$-th) karakterleri $a^rb^sc^s$ ve $a^rb^rc^u$. Bu bunu verir$b=c$bu bir çelişkidir. Bu nedenle,$r=s$.

Yani, $a^rb^rc^r=w$.