Пересечение 2 КЛЛ
Имею следующие два КЛЛ: $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 в строке), вы можете выразить эти последние два условия, сказав, что количество $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)$-й) буквы $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)$-й) символы $a^rb^sc^s$ а также $a^rb^rc^u$. Это дает$b=c$, противоречие. Следовательно,$r=s$.
Так, $a^rb^rc^r=w$.