Насосная лемма для языка, который является регулярным
Я пытаюсь показать, как лемма прокачки применима к языку, который наверняка является регулярным. У меня есть язык {0, 1} с четным числом 1. Этот язык может быть представлен DFA с двумя состояниями.
Таким образом, длина накачки здесь составляет 2, правильно? Лемма накачки гласит, что "если s - любая строка в A длиной по крайней мере p", то она может быть разделена на xyz, так что условия 3 PL выполняются. Допустим, мы выбрали строку "000110" и хотим показать, что каким- то образом ее можно разбить на xyz так, чтобы |xy| <= p (и |y| > 0, а x(y^i)z находится в L).
В этом случае у должно было бы быть "11", чтобы его можно было повторить, и все равно было бы четным... что могло бы составить х = "000", верно? Это тогда сделало бы |xy| = 5, что больше, чем р.
Я не вижу другого способа разбить данную строку так, чтобы | xy | <стр. Что мне здесь не хватает? Спасибо большое.
1 ответ
@Jim Льюис дал ответ на мой вопрос - у нас может быть x = пустая строка, y = '0' и a z = '00110', что позволит нам качать y столько (или столько), сколько мы хотим, удовлетворяя требования насосной леммы. Спасибо!