La intersección de 2 CFL

Aug 20 2020

Tengo las siguientes dos CFL:$A =\{a^m b^n c^n\}$y$B = \{a^m b^m c^n\}$. No entiendo por qué la intersección de estos idiomas es$\{a^n b^n c^n\}$: ¿alguien puede explicarme por qué el poder es para el$n$y no a la$m$¿o algo mas? Gracias de antemano.

Respuestas

1 user6530 Aug 20 2020 at 19:21

El conjunto$A$Cointains todas las cadenas en el alfabeto$\{a,b,c\}$empezando con$a$, terminando con$c$y con el mismo número de$b$arena$c$s. Similarmente,$B$está formado por cadenas en el mismo alfabeto, comenzando con$a$, terminando con$c$y con el mismo número de$a$arena$b$s.

Entonces la intersección$A\cap B$simplemente contiene todas las cadenas en el alfabeto$\{a,b,c\}$empezando con$a$, terminando con$c$, con el mismo número de$b$arena$c$s y el mismo número de$a$arena$b$s. Por la transitividad de la igualdad (quiero decir, si$x=y$y$y=z$después$x=z$, dónde$x$,$y$y$z$son los numeros de$b$s,$c$arena$a$s en una cadena), puede expresar estas dos últimas condiciones diciendo que el número de$a$s,$b$arena$c$s es lo mismo, es decir , que las cadenas en$A\cap B$son de la forma$a^n b^n c^n$para algún número natural$n$(por supuesto aquí puedes usar la letra$m$, o cualquier otra letra que prefieras, en lugar de$n$).

plop Aug 20 2020 at 19:08

Tienes eso$A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$y$B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. Si$w\in A$, entonces hay$r,s\in\mathbb{N}$tal que$w=a^rb^sc^s$. si tambien tenemos eso$w\in B$(tal que$w\in A\cap B$), entonces hay$t,u\in\mathbb{N}$tal que$w=a^tb^tc^u$.

Por lo tanto,$a^rb^sc^s=w=a^tb^tc^u$.

Necesitamos asumir que$a,b,c$son personajes diferentes. De lo contrario, no se satisface la conclusión buscada. Por ejemplo, si$a=b=c$, después$A=B=\{a^n:\ n\in\mathbb{N}\}$, tiempo$A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Esta suposición, si no se dijo explícitamente, probablemente fue intencionada.

Ahora si$r<t$(o$r>t$), luego comparando el$(r+1)$-th (o$(t+1)$-th) letras de$a^rb^sc^s$y$a^tb^tc^u$obtendríamos$a=b$. Esto es una contradicción. Por lo tanto,$r=t$.

Asi que,$a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. Hacemos el mismo análisis con$r$y$s$. Si$r<s$(o$r>s$) comparamos el$(r+1)$-th (o$(s+1)$-th) caracteres de$a^rb^sc^s$y$a^rb^rc^u$. esto da que$b=c$, lo cual es una contradicción. Por lo tanto,$r=s$.

Asi que,$a^rb^rc^r=w$.