Союз детерминированного контекста Свободный язык и обычный язык Результаты?
Данный L1 является детерминированным контекстно-свободным языком, а L2 является обычным языком L1 U L2 результаты DCFL или обычные?
приведите несколько примеров с контекстом
2 ответа
Результирующий язык должен быть DCFL. Интуитивно вы можете проверить, находится ли строка в объединении DCFL и обычного языка, получив DPDA для DCFL, DFA для обычного языка, затем запустив их параллельно и посмотрев, есть ли согласие. Вы можете смоделировать этот процесс, используя вариант конструкции продукта, который показывает, что обычные языки закрыты в объединении: создайте DPDA с одним состоянием для каждой комбинации состояния DFA и состояния DPDA, затем структурируйте переходы так, чтобы они моделировали после перехода от DPDA и DFA параллельно. Для этого вам нужен только один стек, поэтому конструкция должна работать нормально.
Надеюсь это поможет!
l2= сигма * и L1=a^nb^n l1 - это dcfl, а l2 - регулярное. но объединение L1 l2=l1 - это dcfl, но не регулярное