Я сталкивался с таким вопросом: «Приведите примеры двух обычных языков, которые их объединение не выводит на обычном языке».
Это довольно шокирует меня, потому что я считаю, что обычные языки закрыты для объединения. Что означает для меня, что, если я возьму два обычных языка и объединю их, я должен получить обычный язык.
И я думаю, что я понимаю доказательство этого: по моим словам, если языки регулярные, то существуют автоматы, которые их распознают. Если мы возьмем все состояния (объединение) и добавим новое состояние для точки входа и изменим функцию перехода для нового состояния с помощью epsilon, у нас все в порядке. Мы также показываем, что существует путь из каждого штата и т. Д.
Можете ли вы сказать мне, где я не прав, или, возможно, другой способ подойти к вопросу.
Источник вопроса, упражнение 4, на французском языке.
Кроме того, тот же вопрос задается с пересечением.
Ответы:
Существует существенная разница между вопросом, который вы задаете, и вопросом, заданным в упражнении. Вопрос требует примера набора регулярных языков таких, что их объединение не является регулярным. Обратите внимание на диапазон объединения: от до . Обычные языки замкнуты при конечном объединении, и доказательства идут по линиям, которые вы набросали в вопросе, однако при бесконечном объединении это разваливается . Мы можем показать это, взяв для каждого (сL = ∞ ⋃ i = 1 L iL1, Л2, ...
Кроме того, мы можем легко увидеть, где нормальное доказательство не проходит. Представьте себе ту же конструкцию, в которой мы добавляем новое начальное состояние и -transitions к старым начальным состояниям. Если мы сделаем это с бесконечным множеством автоматов, мы получим автоматы с бесконечным числом состояний, очевидно противоречащие определению конечных автоматов.ε
Наконец, я предполагаю, что путаница может возникнуть из-за формулировки первоначального вопроса, который начинается с «Donner deux exampleses des suites de langages ...», то есть (
грубо говоря, мой французский немного ржавый, но внешне проверенный!) «Дайте два примера последовательностей языков ...», а не «Дайте два примера языков ...». Неосторожное чтение может ошибочно принять второе за первое.источник
В качестве второго вопроса рассмотрим языки, определенные как Заметим , что для любого , является регулярным, так как (1) левый множество конечно и , следовательно , регулярным, (2) правый набор обозначается регулярным выражением так регулярно, и (3) регулярные языки закрыты под конечными союзами, как вы уже знаете.
Нетрудно показать, что для любого целого числа у нас есть и, следовательно, поэтому индуктивно имеем (который нам здесь на самом деле не нужен, но он слишком чтобы его не ).M nn≥1 Mn+1⊆Mn Mn∩Mn+1=Mn+1
Теперь внимание, что не содержит , поэтому ни одна из этих строк будет в полном пересечении. В результате у нас будет который, как известно, не является обычным языком. (Если вы не знали этого факта, это есть во многих теоретических текстах, и доказательство того стоит.)Mn an2+1,an2+2,…,a(n+1)2−1
источник
Зачем выбирать сложные регулярные языки, чтобы показать, что регулярные множества не замкнуты в бесконечном объединении? Синглтон-языков достаточно, чтобы показать, что любой язык RE является бесконечным объединением регулярных множеств.
Возьмем любой рекурсивно перечислимого языка . Каждая строка имеет индекс перечисления . Пусть . Каждое - одноэлементное множество, следовательно, регулярное. Но это RE.L w∈L i=index(w) Li={w∣i=index(w)} Li L=⋃∞i=1Li
Аналогично, определяя , мы имеем множества которые являются регулярными в качестве дополнения к одноэлементному набору. Тогда который является дополнением к , следовательно, co-RE. И это может быть достигнуто с любым набором co-RE.Mi=Σ∗∖Li Mi ⋂∞i=1Mi=Σ∗∖L L
Следовательно, любой рекурсивный язык - это бесконечное объединение регулярных множеств, а также бесконечное пересечение регулярных множеств (не те же самые, но их дополнения :).
Бесконечность полна неожиданностей, и то, что верно для произвольно больших значений, может быть неверным на бесконечности.
источник
Если вы выполняете объединение бесконечного множества Unit Unit, вы можете создать любой язык (ну, по крайней мере, любой другой язык, потому что, если он неразрешим, вы не можете указать список всех его строк). Например, объединение наборов единиц, каждый из которых содержит различную строку палиндрома над {a, b}, дает в результате язык палиндрома (без контекста): это{ϵ}⋃{a}⋃{b}⋃{aa}⋃{bb}⋃{aaa}⋃{aba}⋃{bab}⋃{bbb}⋃ ...
Вы можете сделать что-то похожее с пересечением, создавая бесконечное множество множеств, где каждый равен , где - это е слово палиндрома, в результате чего получается язык всех непалиндромных слов (дополнение к языку палиндрома, не -регулярна).Σ∗−{pi} pi i
источник