Язык L = {a ^ mb ^ nc ^ k | если (m = n), то (n = k)} является языком без контекста именно по той причине, которая указана во втором выводе: условие if (m = n), тогда (n = k) не только верно, когда m = n и n = k, но также когда m не равно n. Если бы условия были (m = n) и (n = k), язык не был бы свободен от контекста, поскольку это условие было бы эквивалентно m = n = k.
Мы можем доказать вывод, который показывает язык быть контекстно-корректным, показывая что-либо в L находится в L2, и наоборот.
Предположим, что строка w на нашем языке L. Тогда либо m = n, либо нет. Если m = n, то n = k. Но тогда строка w находится в L2, поскольку L2 является объединением двух языков, один из которых содержит все строки с n = k. Если m = n не так, то строка w находится в L2, потому что L2 является объединением двух языков, другой из которых является языком всех строк, где m и n не равны. Таким образом, любая строка в L находится в L2.
Предположим, что строка w находится в L2. Тогда либо m = n ложно, либо n = k верно. Предположим, что m = n неверно. Тогда условие if (m = n) затем (n = k) является вакуумно верным (поскольку гипотеза неверна, а все вытекает из противоречия). Если n = k истинно, то независимо от истинности значения гипотезы значение if (гипотеза) тогда (n = k) должно быть истинным. Поэтому любая строка в L2 находится в L.
Поскольку L и L2 являются подмножествами друг друга, они должны быть равны.