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

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

0 голосов
/ 01 февраля 2020 
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. Мистер Митл sh Упадхьяй выиграл игру за данный язык.

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

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

Опция (A) верна.

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

...