0
Как a^n b^n, где n> = 1 не является регулярным?
Это простые конечные автоматы, которые я пробовал, что я делаю неправильно?
A
ответ
0
Переход b приводит к окончательному состоянию, которое останавливает машину. Ваша машина остановится только при заданной последовательности «ab» длиной 1 или более.
+0
Я думаю, что машина остановлена только в том случае, если конечная последовательность ввода/разделитель определена. – user
+0
Вы правы. Что вы имеете в виду, не регулярно? –
4
Это соответствия 
, не 
. Aka ababab, а не aaabbb.
0
Язык a^n b^n, где n> 1 не является регулярным, и его можно доказать, используя лемму о перекачке. Предположим, что существует автомат конечного состояния, который может принимать язык. Этот конечный автомат имеет конечное число состояний k, а на языке существует строка x такая, что n> k. Согласно лемме о перекачивании х можно разложить так, что х = иу, и любой конечный автомат, принимающий х, также должен принимать и ^. v непусто и может состоять только из a или только b, так как n> k. Пусть v состоит только из a. Если конечный автомат принимает x = uvw, он также должен принять x = uvvw, который имеет больше a, чем b, и не имеет вида a^n b^n. Это противоречие, поэтому a^n b^n не может быть регулярным языком.
0
Это соответствует (ab)^n, а не^nb^n.
Что вы ищете является Pumping lemma for regular languages.
Примеры:
Пусть L = {а^мб^т | m ≥ 1}.
Тогда L не является регулярным.
Доказательство. Пусть n будет таким же, как в Pumping Lemma.
Пусть w = a^nb^n.
Пусть w = xyz, как в лемме о прокачке.
Таким образом, xy^2z ∈ L, однако xy^2z содержит больше a, чем b.
Как эта вещь должна отслеживать, сколько '' s это видно? Если вы кормите его строкой, начинающейся с 'aaaab', как она будет знать, ей нужно увидеть еще 3' b's? – user2357112
Вы смешиваете это с языком '(ab)^n'? – user2357112