Мне бы очень понравилась ваша помощь в следующем:
Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами:
.
Соответствующие варианты:
Обычные языки закрыты под соответственно A r , для любого языка L 2
Для некоторых языков обычные языки закрыты под A l соответственно. A r , а для некоторых языков L 2 обычные языки не закрыты под A l соответственно. Г .
Я полагал, что ответом для (1) должно быть (2), потому что, когда я получаю слово в и w = x y, я могу построить автомат, который может угадать, где x поворачивается к y , но тогда он должен проверить что у принадлежит L 2, и если он не будет регулярным, как он это сделает?
Ответ на это (1).
Что я должен сделать, чтобы правильно проанализировать эти операторы и определить, закрыты ли под ними обычные языки или нет?
Ответы:
Чтобы ответить на этот вопрос, нам нужно разрешить любой . Итак, давайте подумаем, что L 2 - очень сложный язык (скажем, какой-то неразрешимый язык).L2 L2
Начнем с простого вопроса: (часть вопроса 2). Возьмем L 2, чтобы быть неразрешимым, и L = { ε } . Что происходит?Al(L) L2 L={ε}
(мораль: всегда проверяйте "крайности": пусто , L = { ε } и L = Σ ∗ ...)L L={ε} L=Σ∗
Теперь для . Это отличный вопрос (обычно бонусный вопрос в Final / Homeworks). Действительно, регулярные языки замкнуты относительно A r для любого языка L 2 . Даже неразрешимый L 2 . Круто, верно?Ar Ar L2 L2
Итак, как мы можем построить автомат для если нет машины, которая принимает L 2 ?Ar(L) L2
Здесь приходит магия «абстрактного мышления», т. Е. Экзистенциального доказательства . Если кто-то дает нам мы можем использовать эту информацию, чтобы показать, что существует некоторый автомат для решения A ( L ) . Теперь подробности.L2 A(L)
Начнем с автомата (назовем D F A L ). Предположим, что после обработки x мы окажемся в состоянии q . Нам нужно принять , если существует у ∈ L 2 таким образом, что если мы будем продолжать от д обработки у нас будет в конечном итоге в конечном состоянии D F A L . Не существует машины, которая могла бы сказать нам, находится ли y в L 2 , но мы можем сделать q конечным состоянием D F A A LL DFAL x q y∈L2 q y DFAL y L2 q DFAAL если вышеуказанное условие выполнено, то есть, если существует какой - то таким образом, что , если мы начинаем в ц и процесса у нас в конечном итоге в конечном состоянии D F A L .y∈L2 q y DFAL
Итак, чтобы построить мы исследуем каждое из состояний D F A L и сделаем каждое состояние q принимающим, если мы можем взять некоторый y ∈ L 2, и этот y приведет нас от q к принимающему состоянию Д Р л .DFAAL DFAL q y∈L2 y q DFAL
Итак, бесконечен, и у нас может не быть компьютера для перечисления всех слов в L 2 , но все это не имеет значения ... вышеуказанный автомат четко определен, даже если я не могу его нарисовать для вас государство государством. Магия.L2 L2
источник
Я не уверен, ищете ли вы ответ на проблему или нет, поэтому я не предоставляю его напрямую. (Я могу, если хотите, хотя.)
Ты спрашивал:
Ваш стартовый подход хорош. Как и во всех «открытых» вопросах теории, вы должны интуитивно почувствовать, правда это или нет. Обычно это делается с помощью примеров (как общего, так и крайнего случая) или изучения особых случаев (например, что если является регулярным «контекстно-свободным»). Для этой проблемы вам нужно выработать некоторые предположения относительно того, можете ли вы построить автомат / регулярное выражение для операторов или нет. После того:L2
(и если один подход не работает, вы всегда можете попробовать другой.)
Для самой проблемы:
источник