Дан L1 контекстно-свободный нерегулярный язык. Учитывая обычный язык L2.
Возможно ли, что L1 U L2 = обычный язык? Кроме того, возможно ли, что L1 * L2 = обычный язык?
Я думаю, что 2-й невозможен. Но я не уверен.
Хотелось бы увидеть пример, если одно из вышеупомянутых утверждений (или оба) верно.
Возможно ли, что
L1 U L2= обычный язык?
Да, возможно.
Простой случай: если L1 является подмножеством L2, то L1 U L2 будет обычным (=L2), например: L1 : { anbn | где n >= 0 } и L2 = (a + b)*
возможно ли, что
L1 * L2= обычный язык?
Нет, конкатенация контекстно-свободного и регулярного будет контекстно-свободным (поскольку ограничение в шаблоне L1 все еще присутствует в L1 * L2).
Добавление ссылки: CS 273: Закрытие Свойства для контекстно-свободных языков
Возможно ли, что
L1 U L2= обычный язык?
Да, это возможно. Но всегда лучше брать пример:
L1 = {0*1*} (обычный) и L2 = {0^n1^n |n>=0} (бесконтекстный).
L = L1 U L2 = {0*1*}, который является обычным языком, но поскольку каждый обычный язык не зависит от контекста. Таким образом, мы можем сказать, что объединение двух всегда приводит к контекстно-свободному языку.
Возможно ли, что
L1·L2= обычный язык?
объединение обычного и контекстно-свободного языка всегда приводит к контекстно-свободному языку. Возьмем еще раз приведенный выше пример:
L = L1·L2 = {(0*1*)·(0^n1^n) |n>=0} (без контекста).
Он также может быть обычным, если, например, один из L1 или L2 равен Ø, L1·L2 приведет к Ø (обычный). Но поскольку все обычные языки контекстно-свободны, Ø также является контекстно-свободным.
Проверьте это: Гики для гиков
да, конкатенация контекстно-свободного и регулярного будет регулярным
возьмем L1= a^nb^n, который является CFL, и возьмем L2 = Ø, который является правильным.
поэтому L1.L2 = (a^nb^n).Ø = Ø, что является правильным
Примечание. Чтобы объединение двух языков должно быть регулярным, должен быть хотя бы один язык, чтобы быть регулярным.
