Я не могу понять, является ли этот язык регулярным, может ли он быть представлен с помощью nfa?

Question

Является ли этот язык регулярным?Я не могу найти решение для этого, и у меня смешанные чувства по этому поводу, кстати, я делаю это только последние 2 недели.

Answer 1

Этот язык не является регулярным, и мы можем доказать это, используя лемму прокачки для обычных языков.Предположим, язык был регулярным.Тогда строка 0 ^ p 1 ^ p на языке может быть записана как uvx, где | uv |<= p, | v |> 0 и для всех натуральных чисел k, u (v ^ k) x есть в языке.Тем не менее, наш uv должен состоять только из ведущих 0, и, поскольку мы можем откачать, выбрав k = 0, мы нарушаем | w |<= п.Это противоречие, поэтому язык не может быть регулярным. </p>