Я пытаюсь показать, как лемма перекачки относится к правильному языку. У меня есть язык над {0, 1}, который имеет четное число 1. Этот язык может быть представлен DFA, который имеет два состояния.Накачка леммы для регулярного языка
Таким образом, длина прокачки здесь равна 2, правильно? В лемме о перекачке говорится, что «если s любая строка в A длиной не менее p», то ее можно разделить на xyz так, чтобы выполнялись условия 3 PL. Итак, скажем, мы выберем строку «000110» и хотим показать, что как-то можно разбить на xyz так, что | xy | < = p (и | y |> 0, а x (y^i) z находится в L).
В этом случае y должно быть «11», чтобы его можно было повторить и все еще быть ровным ..., что сделало бы x = '000', правильно? Тогда это сделало бы | xy | = 5, что больше, чем p.
Я не вижу другого способа расщепления данной строки так, чтобы | xy | < p. Что мне здесь не хватает? Огромное спасибо.
Вы также можете нажать «00». –
@JimLewis Итак, я мог бы сделать x = empty, y = '00' (или даже '0'), а z = '0110'? –
Да, оба варианта удовлетворяли бы условиям PL. Основная идея заключается в том, что ваш выбор «y» соответствует циклу в некоторых DFA, которые распознают язык. «x» возвращает вас к первому состоянию цикла, «y» берет вас вокруг цикла, а «z» выводит вас из начала цикла в какое-либо принимающее состояние. –