Pumping Lemma для обычных языков

Question

У меня проблемы с довольно сложным вопросом. Меня просят доказать язык {0^n 1^m 0^n | m, n> = 0} нерегулярно, используя лемму о перекачке. Во всех примерах, которые я видел, язык только поднимается до одной и той же переменной (т. Е. A^n b^n). Поэтому мой вопрос: как выбрать подходящую строку для проверки, является ли этот язык нерегулярным?

Кроме того, после этого вопроса, как только у меня есть строка, как вы разложите строку в форму xyz, где | xy | < = длина откачивания и | y | > = 1?

Answer 1

В примерах, которые вы видели раньше, были разные буквы: n, а затем bs. В данном примере в начале и конце слова находятся n Os. Язык добавляет 0 или более 1s между этими блоками Os.

W в лемме о перекачке разлагается w = x y z с | xy | < = m и | y | > 0, где т - длина накачки. Способ выбора w такой же, как и раньше: вы выбираете его таким образом, чтобы xy полностью находился внутри блока, состоящего из одной буквы. Для a^n b^n слово в L выбрано таким, что xy будет состоять из всего, что, если оно «накачивается», будет больше, чем bs. Таким образом, вам нужно как минимум m, так как для слова должно быть на языке, что означает, что вам нужно выбрать m bs. Самый короткий - w = a^mb^m. Для нового сложного языка выберите слово в этом L, так что xy полностью состоит из Os (в первом блоке), так что если он «накачивается», в первом блоке будет больше Os, чем в последнем блоке - и число 1s в середине не было изменено. Тем не менее, вам нужно включить хотя бы один 1 в исходное слово, иначе есть только один блок Os - и на самом деле перекачиваемые слова - это на этом языке, что означает, что нет противоречия и, следовательно, не является доказательством того, что L нерегулярно.