Доказательство нерегулярности языка - Теория автоматов - Ответ 11686337

С доказательством, что L1 и L2 нерегулярны, я согласен, хотя есть замечания.

1. Нужно начать с "Пусть L1 регулярный. Тогда по лемме о разрастании существует k, для которого выполняется некоторое условие. Рассмотрим

". Иначе непонятно, что такое k, в в доказательстве каждый объект должен быть должным образом объявлен.

2. Нужно отметить, что длина w больше k, как этого требуется в лемме.

3. Не "могу сказать что w = xyz, значит

", а "могу сказать, что w = xyz для некоторых x, y, z, для которых

для всех i". То, что

не следует из w = xyz, поэтому нехорошо писать "значит".

4. Если использовать условие, что |x| <= k в лемме о разрастании ("существуют такие x, y, z, что w = xyz, |y| > 0, xy^iz ∈ L для всех i и |xy| <= k"), то можно не рассматривать случаи b) и c). Это условие очень полезно на практике.

И все-таки из нерегулярности L1 и L2 не следует нерегулярность их объединения. Можно сначала взять пересечение L с некоторым регулярным языком. Если бы L был регулярным, то пересечение было бы тоже.

Вернуться к обсуждению:

Доказательство нерегулярности языка Теория автоматов