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