L'intersezione di 2 CFL

Question

Ho i seguenti due CFL:$A =\{a^m b^n c^n\}$e$B = \{a^m b^m c^n\}$. Non capisco perché l'intersezione di queste lingue sia$\{a^n b^n c^n\}$: qualcuno può spiegarmi perché il potere è al$n$e non al$m$o qualcos'altro? Grazie in anticipo.

Answer 1

Il set$A$contiene tutte le stringhe dell'alfabeto$\{a,b,c\}$Iniziare con$a$, terminando con$c$e con lo stesso numero di$b$sabbia$c$S. Allo stesso modo,$B$è composto da stringhe sullo stesso alfabeto, a partire da$a$, terminando con$c$e con lo stesso numero di$a$sabbia$b$S.

Quindi l'incrocio$A\cap B$contiene semplicemente tutte le stringhe dell'alfabeto$\{a,b,c\}$Iniziare con$a$, terminando con$c$, con lo stesso numero di$b$sabbia$c$s e lo stesso numero di$a$sabbia$b$S. Con la transitività dell'uguaglianza (intendo, se$x=y$e$y=z$poi$x=z$, dove$x$,$y$e$z$sono i numeri di$b$S,$c$sabbia$a$s in una stringa), puoi esprimere queste ultime due condizioni dicendo che il numero di$a$S,$b$sabbia$c$s è lo stesso, cioè , che le stringhe in$A\cap B$sono della forma$a^n b^n c^n$per qualche numero naturale$n$(ovviamente qui puoi usare la lettera$m$, o qualsiasi altra lettera che preferisci, invece di$n$).

Answer 2

Ce l'hai$A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$e$B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. Se$w\in A$, allora ci sono$r,s\in\mathbb{N}$tale che$w=a^rb^sc^s$. Se abbiamo anche quello$w\in B$(tale che$w\in A\cap B$), poi ci sono$t,u\in\mathbb{N}$tale che$w=a^tb^tc^u$.

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

Dobbiamo assumerlo$a,b,c$sono caratteri diversi. Altrimenti la conclusione voluta non è soddisfatta. Ad esempio, se$a=b=c$, poi$A=B=\{a^n:\ n\in\mathbb{N}\}$, mentre$A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Questa ipotesi, se non è stata detta esplicitamente, è stata probabilmente voluta.

Ora se$r<t$(o$r>t$), quindi confrontando il$(r+1)$-esimo (o$(t+1)$-esimo) lettere di$a^rb^sc^s$e$a^tb^tc^u$otterremmo$a=b$. Questa è una contraddizione. Perciò,$r=t$.

Così,$a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. Facciamo la stessa analisi con$r$e$s$. Se$r<s$(o$r>s$) confrontiamo il$(r+1)$-esimo (o$(s+1)$-esimo) caratteri di$a^rb^sc^s$e$a^rb^rc^u$. Questo dà quello$b=c$, il che è un controsenso. Perciò,$r=s$.

Così,$a^rb^rc^r=w$.