L = {a ^ nb ^ nc ^ md ^ m: n> = 1, m> = 1} U {a ^ nb ^ mc ^ md ^ n: n> = 1, m> = 1} isRegular?

Question

Есть много примеров для доказательства насоса, но я не выяснил, кто-нибудь может помочь?

L = {a ^ nb ^ nc ^ md ^ m: n> = 1, м> = 1} U {a ^ nb ^ mc ^ md ^ n: n> = 1, m> = 1}

Answer 1

Рассмотрим обычный язык R = a*b*cd.Пересечение двух обычных языков должно быть обычным языком.Пересечение L и R равно a^n b^n cd.Однако легко показать, что это не регулярно, используя лемму накачки или теорему Майхилла-Нероде.Это противоречие, поэтому L не должно быть регулярным.