2 CFL의 교차점
다음 두 가지 CFL이 있습니다. $A =\{a^m b^n c^n\}$ 과 $B = \{a^m b^m c^n\}$. 이 언어가 교차하는 이유를 이해할 수 없습니다.$\{a^n b^n c^n\}$: 누구든지 힘이 왜 나에게 설명 할 수 있습니까? $n$ 아니라 $m$또는 다른 것? 미리 감사드립니다.
답변
세트 $A$ 알파벳의 모든 문자열을 일치시킵니다. $\{a,b,c\}$ 로 시작 $a$, 끝나는 $c$ 그리고 같은 수의 $b$모래 $c$에스. 비슷하게,$B$ 다음으로 시작하는 동일한 알파벳의 문자열로 만들어집니다. $a$, 끝나는 $c$ 그리고 같은 수의 $a$모래 $b$에스.
그래서 교차로 $A\cap B$ 단순히 알파벳의 모든 문자열을 일치시킵니다. $\{a,b,c\}$ 로 시작 $a$, 끝나는 $c$, 동일한 수 $b$모래 $c$s 및 동일한 수 $a$모래 $b$에스. 평등의 전이성 (내 말은$x=y$ 과 $y=z$ 그때 $x=z$, 어디 $x$, $y$ 과 $z$ 숫자는 $b$에스, $c$모래 $a$s in a string),이 마지막 두 조건을 표현할 수 있습니다. $a$에스, $b$모래 $c$S는, 동일 즉 문자열에있는 것을$A\cap B$ 형태이다 $a^n b^n c^n$ 자연수를 위해 $n$ (물론 여기서 편지를 사용할 수 있습니다. $m$, 또는 원하는 다른 문자 대신 $n$).
당신은 그것을 가지고 $A=\{a^mb^nc^n:\ m,n\in\mathbb{N}\}$ 과 $B=\{a^mb^mc^n:\ m,n\in\mathbb{N}\}$. 만약$w\in A$, 다음이 있습니다 $r,s\in\mathbb{N}$ 그런 $w=a^rb^sc^s$. 그것도 가지고 있다면$w\in B$ (그런 $w\in A\cap B$), 다음이 있습니다. $t,u\in\mathbb{N}$ 그런 $w=a^tb^tc^u$.
따라서, $a^rb^sc^s=w=a^tb^tc^u$.
우리는 $a,b,c$다른 캐릭터입니다. 그렇지 않으면 원하는 결론이 충족되지 않습니다. 예를 들어$a=b=c$, 다음 $A=B=\{a^n:\ n\in\mathbb{N}\}$, 동안 $A\cap B= A\neq\{a^na^na^n:\ n\in\mathbb{N}\}$. 이 가정은 명시 적으로 말하지 않았다면 아마도 의도 된 것입니다.
자, 만약 $r<t$ (또는 $r>t$), 다음 비교 $(r+1)$-토르 $(t+1)$-th) 편지 $a^rb^sc^s$ 과 $a^tb^tc^u$ 우리는 얻을 것이다 $a=b$. 이것은 모순입니다. 따라서,$r=t$.
그래서, $a^rb^sc^s=a^rb^sc^s=w=a^tb^tc^u=a^rb^rc^u$. 우리는$r$ 과 $s$. 만약$r<s$ (또는 $r>s$) 우리는 $(r+1)$-토르 $(s+1)$-th) 문자 $a^rb^sc^s$ 과 $a^rb^rc^u$. 이것은$b=c$, 이것은 모순입니다. 따라서,$r=s$.
그래서, $a^rb^rc^r=w$.