Является ли

Я сдал экзамены по теории вычислений несколько недель назад, и это был один из вопросов:

Предположим, что язык$L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

L регулярно? Если да, укажите для него регулярное выражение или автомат.

После того, как я кратко спросил его ответ после экзамена, кажется, что он действительно правильный (я думаю, он сказал, что это простое выражение ). Однако я не могу понять, почему это так. То, как я это вижу, это конкатенация r раз, вот так:$(a^*b^*)^*$$a^nb^m$

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

что не является регулярным, поскольку у автомата нет способа каждый раз вызывать n и m . Где я здесь виноват?

РЕДАКТИРОВАТЬ: Я снова говорил с профессором, он признал, что это было ошибкой. Язык действительно не обычный.

Язык не является регулярным, что можно доказать с помощью метода Нерода. Рассмотрим следующие слова W п = а п Ь для п ∈ N . Тогда ш 2 п ∈ L , но для п ≠ м , ш п ш т ∉ L . Следовательно, после считывания каждого w n любой автомат для L должен находиться в другом состоянии , что противоречит его конечности.$L$$w_n = a^n b$$n \in \mathbb{N}$$w_n^2 \in L$$n \neq m$$w_n w_m \notin L$$L$$w_n$

В своем комментарии вы намекаете, что вы (цитируете) «дали опровержение леммы прокачки для , сказав то же самое для большего r ».$r=2$$r$

Это действительно может быть формализовано путем применения свойства замыкания. Обычные языки закрыты на пересечении. Таким образом, если является регулярным, то так будет L ∩ a ∗ b a ∗ b = { a n b a n b ∣ n ≥ 0 } , эффективно устанавливая r = 2 и m = 1 .$L$$L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$$r=2$$m=1$

Язык: {(a ⁿ b ^m ) ^r | n, m, r≥0} не является регулярным, потому что, в то время как автомат / машина читает первую последовательность букв «a», а затем буквы «b», ему необходимо посчитать, сколько раз он прочитал букву «a» и сколько раз он прочитал букву «b» в первой последовательности, чтобы узнать значения n и m .

Если r> 1, то ожидается другая та же последовательность букв «a» и букв «b».

Если автомат / аппарат не не знает , сколько букв «а» и буквы «Ъ» он прочитал в первой последовательности , то она также имеет не знать значение п и м и , таким образом , он может не если сказать другие последовательности от второго до последнего являются словами, которые равны первой последовательности.

Но известно, что только машина Тьюринга может считать и знать значения n и m и распознавать язык выше, поэтому не только то, что язык выше не является регулярным, но даже он также не является контекстно-свободным, т.е. Не существует автомат для распаковки для распознавания этого языка, и не существует контекстно-свободной грамматики, в которой каждое слово, полученное из этой контекстно-свободной грамматики, находится на вышеуказанном языке.

Поскольку тот факт, что как детерминированный конечный автомат, так и конечный автомат с понижением не могут считать и знать значения n и m , в отличие от машины Тьюринга, они не могут распознать вышеуказанный язык, и, следовательно, указанный выше язык не является контекстно-свободным и не является регулярным.

Контрпример к предположению, что язык выше является регулярным:

Для n = 3 m = 5 r = 2 следующее слово на вышеуказанном языке:

aaabbbbbaaabbbbb

Но следующего слова нет в языке:

aaabbbbbaaaaabbb, потому что n, m и r не существует так:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, потому что для удовлетворения первой последовательности букв «a», а затем букв «b» должно быть верно, что n = 3 ∧ m = 5 , и потому что мы видим 2 последовательности букв ' a 'и затем буквы' b ', тогда r = 2 , но если n = 3 ∧ m = 5 2 r = 2, то (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, потому что их суффиксы разные, т.е. aaabbbbb ≠ aaaaabbb, хотя их префиксы равны aaabbbbb при r = 1.

«Лучший» детерминированный конечный автомат, который может быть построен для этого языка, - это детерминированный конечный автомат, который распознает регулярное выражение (a * b *) *, но не распознает вышеуказанный язык, потому что он говорит, что оба слова aaabbbbbaaabbbbb и aaabbbbbaaaaabbb на языке, и это не так, потому что aaabbbbbaaabbbbb на языке, но aaabbbbbaaaaabbb не на языке.

Даже конечный автомат не может сказать, есть ли оба слова в языке или нет, так что только машина Тьюринга может.

Во второй последовательности машина Тьюринга обнаружила, что n = 5 ∧ m = 3, и это противоречит тому, что в первой последовательности она обнаружила, что n = 3 ∧ m = 5 , поэтому она говорит, что второго слова нет в языке , но в первом слове нет противоречия.

Обе последовательности удовлетворяют тому, что n = 3 ∧ m = 5 , поэтому машина Тьюринга говорит, что первое слово в языке.

Только машина Тьюринга может, если она считает и запоминает значения n и m , записывая их значения на своей ленте, а затем считывает их.