РЕДАКТИРОВАТЬ: я сделал 2 ошибки здесь, во-первых, прокачка должна быть связана с словом, которое вы используете (или, по крайней мере, так кажется после просмотра большого количества примеров), во-вторых, наоборот, если вы найдете какое-либо хорошее соответствие , то вы не можете использовать это как неправильный пример. При условии, что мой ответ был неверным, я отредактирую, как это можно доказать.
Лемма об откачивании заключается в том, чтобы доказать, что это не обычный язык, используя противоречие. Сначала вы должны предположить, что предоставленная вами строка, которая должна быть действительной для L, является регулярной, затем вы должны разделить эту строку на 3 части, следуя некоторым правилам. :
- | у | > 0
- | х | <= P (P представляет минимальную длину слова) </li>
- xy ^ nz с n> = 0 включено в язык (L)
Итак, давайте возьмем, например, P равно 1:
Для использования этого я не буду использовать никакие b, если язык позволяет это.
Это означает, что мой язык будет выражаться следующим образом: L = {a ^ P + 1 c ^ P}, который включен в L и допустим, поэтому допустим, что aac (этот находится в L)
- Единственный способ разделить это (x: a, y: a, z: c)
Имея это в виду, вы можете доказать нерегулярно, используя 2 из 3 утверждений
| х | больше, чем P, потому что P равно 1, а xy равно 2
xy ^ nz, если мы используем n = 0, то результатом будет ac, который не включен в язык.