нагнетательная лемма для очень простого регулярного выражения

Question

Определение леммы о откачке (от wiki)

Позвольте L быть обычным языком. Тогда существует целое число p ≥ 1, зависящее только от L такое, что каждая строка w в L длины не менее p (p называется «длиной накачки» [4]) может быть записана как w = xyz (т. Е. W может быть разделенных на три подстроки), удовлетворяющих следующим условиям:

| y | ≥ 1; | xy | ≤ р при всех ≥ 0, xyiz ∈ L

Предположим, что необходимо проверить регулярное выражение 011 Поскольку регулярная expressionm, есть строка ж, по крайней мере, длины р, которые удовлетворяют ш = хуг

The число этих автоматов равно 3, p должно быть> = 3 Но только строка, принимающая этот автомат, равна 011 Итак, я выбираю 011 как w Я могу разбить 3 часть 011 = xyz , но как я могу сломаться? Я не могу удовлетворить | y | ≥ 1; | xy | ≤ p для всех i ≥ 0, xyiz ∈ L

Поскольку принимается только 011 Как я могу перекачивать? Где я ошибаюсь

Answer 1

Пусть р быть 4. Тогда нет строки ж в L длины, по меньшей мере р, так что любое утверждение вида «каждая строка ш в L длиной не менее p [& hellip;] "будет vacuously true. Таким образом, лемма накачки выполняется.