A interseção de 2 CFL

Question

Eu tenho os dois CFL a seguir:$A =\{a^m b^n c^n\}$e$B = \{a^m b^m c^n\}$. Eu não entendo porque a interseção dessas línguas é$\{a^n b^n c^n\}$: alguém pode me explicar por que o poder é para o$n$e não ao$m$ou alguma outra coisa? Agradeço antecipadamente.

Answer 1

O conjunto$A$contém todas as strings do alfabeto$\{a,b,c\}$começando com$a$, terminando com$c$e com o mesmo número de$b$areia$c$s. De forma similar,$B$é feito por strings no mesmo alfabeto, começando com$a$, terminando com$c$e com o mesmo número de$a$areia$b$s.

Então a interseção$A\cap B$simplesmente contém todas as strings do alfabeto$\{a,b,c\}$começando com$a$, terminando com$c$, com o mesmo número de$b$areia$c$s e o mesmo número de$a$areia$b$s. Pela transitividade da igualdade (quero dizer, se$x=y$e$y=z$então$x=z$, Onde$x$,$y$e$z$são os números de$b$s,$c$areia$a$s em uma string), você pode expressar essas duas últimas condições dizendo que o número de$a$s,$b$areia$c$s é o mesmo, ou seja , que as strings em$A\cap B$são da forma$a^n b^n c^n$para algum número natural$n$(claro que aqui você pode usar a letra$m$, ou qualquer outra letra que você preferir, em vez de$n$).

Answer 2

Você tem isso$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$, então existem$r,s\in\mathbb{N}$de tal modo que$w=a^rb^sc^s$. Se também tivermos isso$w\in B$(de tal modo que$w\in A\cap B$), então existem$t,u\in\mathbb{N}$de tal modo que$w=a^tb^tc^u$.

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

Precisamos supor que$a,b,c$são personagens diferentes. Caso contrário, a conclusão desejada não é satisfeita. Por exemplo, se$a=b=c$, então$A=B=\{a^n:\ n\in\mathbb{N}\}$, enquanto$A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. Essa suposição, se não foi explicitamente dita, provavelmente foi intencional.

Agora se$r<t$(ou$r>t$), então comparando o$(r+1)$-th (ou$(t+1)$-th) letras de$a^rb^sc^s$e$a^tb^tc^u$nós conseguiríamos$a=b$. Isso é uma contradição. Portanto,$r=t$.

Então,$a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. Fazemos a mesma análise com$r$e$s$. Se$r<s$(ou$r>s$) comparamos o$(r+1)$-th (ou$(s+1)$-th) caracteres de$a^rb^sc^s$e$a^rb^rc^u$. isso dá aquilo$b=c$, o que é uma contradição. Portanto,$r=s$.

Então,$a^rb^rc^r=w$.