#regular-language
#обычный язык
Вопрос:
Лемма о накачке используется для доказательства того, что язык не является регулярным. Но как можно
доказать, что язык является регулярным? В частности,
Let L be a language. Define half(L) to be
{ x | for some y such that |x| = |y|, xy is in L}.
Prove for each regular L that half(L) is regular.
Существует ли какой-либо трюк или общая процедура для решения такого рода вопросов?
Ответ №1:
Если вы сможете правильно описать свой язык L с помощью NFA или DFA, то он будет обычным.
Существует хорошо известное равенство NFA, DFA, регулярных грамматик и регулярных выражений, поэтому представление L в любом из этих формализмов должно подходить.
Ответ №2:
Предоставьте обычную грамматику или конечный автомат, соответствующий языку. Полный список свойств, которые вы можете доказать, чтобы показать, что язык является регулярным, смотрите в первых строках статьи Википедии о регулярных языках.
Комментарии:
1. 1 за то, что заставил меня анализировать (неудачный каламбур) «[Обычный язык] является прообразом подмножества конечного моноида при гомоморфизме от свободного моноида в его алфавите».
2. К счастью, вам нужно выбрать только один из этих маркированных пунктов, если вы просто хотите доказать, что язык является регулярным.