Почему данный язык является нерегулярным? Дискретная математика. L={a^n b^n | n принадлежит N объединение 0}. Почему данный язык не является регулярным? Ведь a^n - регулярный язык и b^n - регулярный язык, а конкатенация регулярных языков - является регулярным языком. Но в данном случае почему-то не регулярный получился

Предыдущий
вопрос Следующий
вопрос

Данный язык L = {a^n b^n | n принадлежит N объединение 0} не является регулярным, потому что он не удовлетворяет условию леммы о накачке для регулярных языков. Другими словами, для данного языка невозможно найти такое число p (называемое константой накачки), что любое слово языка длиной больше p можно разбить на три части так, чтобы после повторения любого количества раз одной из частей результат все еще принадлежал бы языку L.

В данном случае, если мы возьмем слово w = a^p b^p, где |w| >= p, и будем пытаться накачивать его, то мы обязательно нарушим условие a^n b^n, так как не сможем поддержать равенство количества символов a и b.

Таким образом, хотя языки a^n и b^n действительно являются регулярными, их объединение в данном случае не может быть выражено регулярным языком, и, следовательно, язык L не является регулярным.