Закрытие против правильного отношения с фиксированным языком

13

Мне бы очень понравилась ваша помощь в следующем:

Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами:L2

  1. Ar(L)={xyL2:xyL}

  2. .Al(L)={xyL:xyL2}

Соответствующие варианты:

  1. Обычные языки закрыты под соответственно A r , для любого языка L 2AlArL2

  2. Для некоторых языков обычные языки закрыты под A l соответственно. A r , а для некоторых языков L 2 обычные языки не закрыты под A l соответственно. Г .L2AlArL2AlAr

Я полагал, что ответом для (1) должно быть (2), потому что, когда я получаю слово в и w = x y, я могу построить автомат, который может угадать, где x поворачивается к y , но тогда он должен проверить что у принадлежит L 2, и если он не будет регулярным, как он это сделает? Ответ на это (1).wLw=xyxyyL2

Что я должен сделать, чтобы правильно проанализировать эти операторы и определить, закрыты ли под ними обычные языки или нет?

Юзеф
источник
Что такое ? Вы имеете в виду « не закрыты» во второй части (б)? Что такое L ? AL
Алекс тен Бринк
Вы до сих пор не определили ? L
Гопи
@Gopi - это язык ввода. A ( ) является оператором для языков в обоих случаях. LA()
Лукас Кук
@Gopi: - это параметр A , L 2 фиксированный. LAL2
Рафаэль
Упс, мой плохой, как я этого не увидел oO.
Гопи

Ответы:

11

Чтобы ответить на этот вопрос, нам нужно разрешить любой . Итак, давайте подумаем, что L 2 - очень сложный язык (скажем, какой-то неразрешимый язык).L2L2


Начнем с простого вопроса: (часть вопроса 2). Возьмем L 2, чтобы быть неразрешимым, и L = { ε } . Что происходит?Al(L)L2L={ε}

(мораль: всегда проверяйте "крайности": пусто , L = { ε } и L = Σ ...)LL={ε}L=Σ


Теперь для . Это отличный вопрос (обычно бонусный вопрос в Final / Homeworks). Действительно, регулярные языки замкнуты относительно A r для любого языка L 2 . Даже неразрешимый L 2 . Круто, верно?ArArL2L2

Итак, как мы можем построить автомат для если нет машины, которая принимает L 2 ?Ar(L)L2

Здесь приходит магия «абстрактного мышления», т. Е. Экзистенциального доказательства . Если кто-то дает нам мы можем использовать эту информацию, чтобы показать, что существует некоторый автомат для решения A ( L ) . Теперь подробности.L2A(L)

Начнем с автомата (назовем D F A L ). Предположим, что после обработки x мы окажемся в состоянии q . Нам нужно принять , если существует у L 2 таким образом, что если мы будем продолжать от д обработки у нас будет в конечном итоге в конечном состоянии D F A L . Не существует машины, которая могла бы сказать нам, находится ли y в L 2 , но мы можем сделать q конечным состоянием D F A A LLDFALxqyL2qyDFALyL2qDFAALесли вышеуказанное условие выполнено, то есть, если существует какой - то таким образом, что , если мы начинаем в ц и процесса у нас в конечном итоге в конечном состоянии D F A L .yL2qyDFAL

Итак, чтобы построить мы исследуем каждое из состояний D F A L и сделаем каждое состояние q принимающим, если мы можем взять некоторый y L 2, и этот y приведет нас от q к принимающему состоянию Д Р л .DFAALDFALqyL2yqDFAL

Итак, бесконечен, и у нас может не быть компьютера для перечисления всех слов в L 2 , но все это не имеет значения ... вышеуказанный автомат четко определен, даже если я не могу его нарисовать для вас государство государством. Магия.L2L2

Ран Г.
источник
Похоже, вы отправили ответ на саму проблему в то же время. :]
Лукас Кук
хорошо ... в моем ответе есть спойлеры .. может быть, я должен поставить предупреждение о спойлере, чтобы можно было начать с вашего ответа, а если этого недостаточно, то получить подробности ..
Ран Г.
Вау, прекрасный ответ, очень полезно. Большое спасибо, Ран!
Йозеф
7

Я не уверен, ищете ли вы ответ на проблему или нет, поэтому я не предоставляю его напрямую. (Я могу, если хотите, хотя.)

Ты спрашивал:

Что я должен сделать, чтобы правильно проанализировать эти операторы и определить, закрыты ли под ними обычные языки или нет?

Ваш стартовый подход хорош. Как и во всех «открытых» вопросах теории, вы должны интуитивно почувствовать, правда это или нет. Обычно это делается с помощью примеров (как общего, так и крайнего случая) или изучения особых случаев (например, что если является регулярным «контекстно-свободным»). Для этой проблемы вам нужно выработать некоторые предположения относительно того, можете ли вы построить автомат / регулярное выражение для операторов или нет. После того:L2

  • Если вы думаете , что вы можете, вы должны быть в состоянии построить этот автомат / регулярное выражение для любого регулярного входного языка .L
  • Если вы думаете, что не можете, вы обычно найдете примеры языков и L 2, такие, что A x не является замкнутым.LL2Ax

(и если один подход не работает, вы всегда можете попробовать другой.)


Для самой проблемы:

Al(L)=L2/LAr(L)=L/L2L2

ArAlAlL2L2AlL2AlAl L2

Лукас Кук
источник