Обнаружение ошибки в доказательстве с указанием языка L = {0^(n) 1^(n) | п> 0} является регулярным выражением

Question

Доказательство: Пусть М следующая НКА:

Automata for L Теперь, если х в L, то х = 0^(п) 1^(п). Таким образом, при обработке x, M начнет в состоянии q0, зациклирует в состоянии q0 n раз, затем перейдет в состояние q1 на первом 1 и будет следовать за циклом в состоянии q1 в сумме n 1 раз. Поскольку он заканчивается в состоянии q1, x будет принят. Таким образом, M распознает каждую строку в L, поэтому L является узнаваемой NFA (и по теореме Клейна, таким образом, является регулярной).

Answer 1

Вы показали, что M принимает каждую строку L. Но это не значит, что M распознает L: для этого, чтобы быть истинным, вы также должны показать, что M принимает точно строки L и другие (или эквивалентно: он не принимает ни одну строку, а не в L). К сожалению, в вашем случае M делает принимает некоторые строки, отличные от L: например, "011".

Answer 2

Ваше доказательство действительно неверно. Для того, чтобы доказать, что язык L является регулярным вам нужно доказать, что существует конечный автомат М, распознающий язык L. Таким образом, есть три вещи, которые вы должны доказать о автомата М:

1. Автомат М существует.
2. Автомат M распознает язык L (не более, не что иное).
3. Автомат M имеет конечное число состояний.

Проблема с доказательством является то, что автомат вы вывесили не распознает язык L:

Этот автомат распознает язык 0*1+, который не является такой же, как язык L (0^n1^n). Да, каждая строка в L распознается этим автоматом. Однако этот автомат также распознает строки, такие как 1, который явно не находится в L. Следовательно, использование этого автомата в вашем доказательстве неверно.

Итак, как вы доказываете, что автомат M существует? Ну, единственный способ доказать, что автомат М существует, - это показать, что существует М. Единственная проблема заключается в том, что L не является регулярным языком. Следовательно, не существует конечного автомата M, который распознает L.

Противоположный путь состоит в том, чтобы доказать, что L не является обычным языком. Чтобы доказать, что L не является правильным языком, вам нужно доказать, что нет конечного автомата M, который распознает L. Это более простое доказательство, потому что вам не нужно найти автомат M. Вы можете просто предположить, что он существует.

Вот что вам нужно сделать, чтобы доказать, что L не является регулярным языком:

1. Предположим, что автомат M существует, что распознает язык L.
2. Покажите, что M обязательно должен иметь бесконечное число состояний.

Стандартным способом доказательства того, что автомат M не может иметь конечное число состояний, является использование Pumping Lemma. Я оставлю это упражнением для вас, чтобы понять это, потому что это не входит в сферу вашего вопроса.