Минимальная длина откачки L= {0^i1^j | i ›= j}, чтобы доказать, что L не является регулярным

Both Mr. Mithlesh Upadhyay and You play a game:
1. Mr. Mithlesh Upadhyay gives you a constant n.
2. You choose a word w in the language of length at least n.
3. Mr. Mithlesh Upadhyay gives you x, y, and z with xyz = w, |xy|≤n, and y not empty.
4. Now you pick r.
5. Mr. Mithlesh Upadhyay asserts that xyrz is also in the language.
6. If Mr. Mithlesh Upadhyay is wrong, you win.

    In case, if you win the game, what is the minimum possible value of 
your r for the language {0^i1^j | i >= j} ?

A. 0

B. 2

C. 3

D. Г-н Митлеш Упадхьяй выиграл игру для данного языка.

Объяснение Приведенная выше игра известна как лемма о прокачке для обычных языков.

Вы выиграли игру, поскольку минимальное значение r равно 0.

Вариант (А) правильный.

Я не мог понять решение. Как можно получить 0 length min длина накачки. Если мы возьмем w = 01 и накачаем 1 , то она не принадлежит L. Итак, почему 2 не является минимальной длиной ?


regular-language pumping-lemma
person Olivia Pearls    schedule 01.02.2020    source источник
comment
Вы выбираете слово w, и оно должно быть не меньше длины n. Ожидается, что вы выберете строку 0^n1^n, заставив Митлеша разложить так, что y должно быть равно 0^k для некоторого k>=1. В этом случае выбор r=0 приводит к тому, что строка xy^rz принимает форму 0^(n-k)1^n, которой нет в языке. Накачка (с помощью r=2 или r=3) приводит к строке формы 0^(n+k)1^n, которая все еще присутствует в языке.   -  person Welbog    schedule 03.02.2020

Ответы (1)


arrow_upward
1
arrow_downward

Согласно пунктам 5 и 6, если вы победили, это означает, что г-н Митлеш Упадхьяй был неправ и xyrz не принадлежит L. В своем примере вы показали, что 011 не принадлежит L. Если вы собираетесь сделайте минимально возможную длину r равной 2, тогда ваш пример будет неправильным. Потому что вы взяли, что r имеет длину 1. Поправьте меня, если я ошибаюсь.

person Prateekshya Priyadarshini    schedule 03.06.2020