У меня проблемы с довольно сложным вопросом. Меня просят доказать язык {0 ^ n 1 ^ m 0 ^ n | m, n> = 0} нерегулярно по лемме о накачке. Во всех примерах, которые я видел, язык повышается только до одной и той же переменной (т.е. a ^ n b ^ n). Итак, мой вопрос: как мне выбрать подходящую строку, чтобы проверить, не является ли этот язык неправильным?
Также продолжение этого вопроса: как только у меня будет строка, как разложить строку в форму xyz, где | xy | ‹= Длина откачки и | y | > = 1?
В примерах, которые вы видели ранее, были разные буквы: n, за которыми следовала bs. В данном примере это n Os в начале и в конце слова. Язык добавляет 0 или более единиц между этими блоками Os.
W в лемме о накачке разлагается w = x y z с | xy | ‹= M и | y | > 0, где m - длина откачки. Способ выбора w такой же, как и раньше: вы выбираете его так, чтобы xy полностью находился внутри блока, состоящего из одной буквы. Для a ^ n b ^ n было выбрано слово в L так, что xy полностью состояло бы из as, так что если его «накачать», будет больше as, чем bs. Итак, вам нужно как минимум m as и для того, чтобы слово было на языке, который означает, что вам нужно выбрать m bs. Самый короткий - w = a ^ mb ^ m. Для нового проблемного языка выберите слово в этом L так, чтобы xy состояло полностью из Os (в первом блоке), так что если он `` перекачивается '', в первом блоке будет больше Os, чем в последнем блоке, и количество единиц в середине не изменилось. Однако вам необходимо включить хотя бы одну единицу в исходное слово, иначе будет только один блок из Os - а накачанные слова на самом деле присутствуют в языке, что означает отсутствие противоречия и, следовательно, не доказательство. что L нерегулярна.
