L'intersection du 2 CFL

Question

J'ai les deux CFL suivants :$A =\{a^m b^n c^n\}$et$B = \{a^m b^m c^n\}$. Je ne comprends pas pourquoi l'intersection de ces langues est$\{a^n b^n c^n\}$: quelqu'un peut-il m'expliquer pourquoi le pouvoir est au$n$et non à la$m$ou autre chose? Merci en avance.

Answer 1

L'ensemble$A$contient toutes les chaînes de l'alphabet$\{a,b,c\}$commençant par$a$, se terminant par$c$et avec le même nombre de$b$sable$c$s. De la même manière,$B$est composé de chaînes sur le même alphabet, commençant par$a$, se terminant par$c$et avec le même nombre de$a$sable$b$s.

Donc le carrefour$A\cap B$contient simplement toutes les chaînes de l'alphabet$\{a,b,c\}$commençant par$a$, se terminant par$c$, avec le même nombre de$b$sable$c$s et le même nombre de$a$sable$b$s. Par la transitivité de l'égalité (je veux dire, si$x=y$et$y=z$alors$x=z$, où$x$,$y$et$z$sont les nombres de$b$s,$c$sable$a$s dans une chaîne), vous pouvez exprimer ces deux dernières conditions en disant que le nombre de$a$s,$b$sable$c$s est le même, c'est-à -dire que les chaînes dans$A\cap B$sont de la forme$a^n b^n c^n$pour un nombre naturel$n$(bien sûr, ici, vous pouvez utiliser la lettre$m$, ou toute autre lettre que vous préférez, au lieu de$n$).

Answer 2

Tu as ça$A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$et$B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. Si$w\in A$, alors il y a$r,s\in\mathbb{N}$tel que$w=a^rb^sc^s$. Si on a aussi ça$w\in B$(tel que$w\in A\cap B$), alors il y a$t,u\in\mathbb{N}$tel que$w=a^tb^tc^u$.

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

Nous devons supposer que$a,b,c$sont des caractères différents. Sinon, la conclusion recherchée n'est pas satisfaite. Par exemple, si$a=b=c$, alors$A=B=\{a^n:\ n\in\mathbb{N}\}$, pendant que$A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Cette hypothèse, si elle n'a pas été explicitement dite, était probablement voulue.

Maintenant si$r<t$(ou alors$r>t$), puis en comparant$(r+1)$-ème (ou$(t+1)$-th) lettres de$a^rb^sc^s$et$a^tb^tc^u$nous obtiendrions$a=b$. C'est une contradiction. Donc,$r=t$.

Alors,$a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. On fait la même analyse avec$r$et$s$. Si$r<s$(ou alors$r>s$) on compare le$(r+1)$-ème (ou$(s+1)$-th) caractères de$a^rb^sc^s$et$a^rb^rc^u$. Cela donne ça$b=c$, ce qui est contradictoire. Donc,$r=s$.

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