Persimpangan 2 CFL

Question

Saya memiliki dua CFL berikut: $A =\{a^m b^n c^n\}$ dan $B = \{a^m b^m c^n\}$. Saya tidak mengerti mengapa persimpangan bahasa ini$\{a^n b^n c^n\}$: Adakah yang bisa menjelaskan kepada saya mengapa kekuatan itu untuk $n$ dan bukan ke $m$atau sesuatu yang lain? Terima kasih sebelumnya.

Answer 1

Set $A$ cointains semua string pada alfabet $\{a,b,c\}$ dimulai dengan $a$, diakhiri dengan $c$ dan dengan jumlah yang sama $b$s dan $c$s. Demikian pula,$B$ dibuat dengan string pada alfabet yang sama, dimulai dengan $a$, diakhiri dengan $c$ dan dengan jumlah yang sama $a$s dan $b$s.

Jadi perempatannya $A\cap B$ hanya cointains semua string pada alfabet $\{a,b,c\}$ dimulai dengan $a$, diakhiri dengan $c$, dengan jumlah yang sama $b$s dan $c$s dan jumlah yang sama $a$s dan $b$s. Dengan transitivitas persamaan (maksud saya, jika$x=y$ dan $y=z$ kemudian $x=z$, dimana $x$, $y$ dan $z$ adalah jumlah $b$s, $c$s dan $a$s dalam sebuah string), Anda dapat mengekspresikan dua kondisi terakhir ini dengan mengatakan bahwa bilangan $a$s, $b$s dan $c$s adalah sama, yaitu string di$A\cap B$ adalah dari bentuknya $a^n b^n c^n$ untuk beberapa bilangan asli $n$ (tentu saja di sini Anda bisa menggunakan surat itu $m$, atau surat lain yang Anda sukai, daripada $n$).

Answer 2

Anda punya itu $A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$ dan $B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. Jika$w\in A$, lalu ada $r,s\in\mathbb{N}$ seperti yang $w=a^rb^sc^s$. Jika kita juga punya itu$w\in B$ (seperti yang $w\in A\cap B$), lalu ada $t,u\in\mathbb{N}$ seperti yang $w=a^tb^tc^u$.

Karena itu, $a^rb^sc^s=w=a^tb^tc^u$.

Kita perlu berasumsi seperti itu $a,b,c$adalah karakter yang berbeda. Jika tidak, kesimpulan yang diinginkan tidak memuaskan. Misalnya, jika$a=b=c$, kemudian $A=B=\{a^n:\ n\in\mathbb{N}\}$, sementara $A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Asumsi ini, jika tidak dikatakan secara eksplisit, mungkin memang dimaksudkan.

Sekarang, jika $r<t$ (atau $r>t$), lalu membandingkan $(r+1)$-th (atau $(t+1)$-th) huruf $a^rb^sc^s$ dan $a^tb^tc^u$ kami akan mendapatkan $a=b$. Ini adalah kontradiksi. Karena itu,$r=t$.

Begitu, $a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. Kami melakukan analisis yang sama dengan$r$ dan $s$. Jika$r<s$ (atau $r>s$) kami membandingkan $(r+1)$-th (atau $(s+1)$-th) karakter $a^rb^sc^s$ dan $a^rb^rc^u$. Ini memberikan itu$b=c$, yang merupakan kontradiksi. Karena itu,$r=s$.

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