Указанные языки и , скажем , что их конкатенация является однозначной , если для всех слов , существует ровно один разложение с и , и неоднозначном иначе. (Я не знаю, есть ли установленный термин для этого свойства - трудная вещь для поиска!) В качестве тривиального примера, конкатенация с самим собой неоднозначна ( ), но сцепление с самим собой однозначно.
Существует ли алгоритм для определения того, является ли объединение двух регулярных языков однозначным?
Ответы:
Подсказка: учитывая DFA для и , создайте NFA, который принимает слова в имеющие как минимум два разных разложения. NFA отслеживает две копии стандартного NFA для (сформированных путем объединения DFA для и с переходами ), обеспечивая переключение с на в двух разных точках.A A B A B A B ϵ A BB AB AB A B ϵ A B
источник
Обновлено (спасибо Yuval Filmus).
Для двух языков и Y в A ∗ пусть X - 1 YX Y A∗
Я утверждаючтоХYявляется однозначным тогда и только тогдакогдаязыкеХ-1X∩YY-1∩+пуст.
Доказательство . Предположим, что неоднозначно. Тогда существует слово ¯u , который имеет два разложения над X Y , скажем , у = х 1 у 2 = х 2 у 1 , где х 1 , х 2 ∈ Х и у 1 , у 2 ∈ Y . Без ограничения общности можно считать, что x 1 является префиксом x 2 , то есть x 2 = xXY u XY u=x1y2=x2y1 x1,x2∈X y1,y2∈Y x1 x2 для некоторого z ∈ A + . Отсюда следует, что u = x 1 y 2 = x 1 z y 1 , откуда y 2 = z y 1 . Таким образом, z ∈ X - 1 X ∩ Y Y - 1 .x2=x1z z∈A+ u=x1y2=x1zy1 y2=zy1 z∈X−1X∩YY−1
Предположим теперь, что содержит некоторое непустое слово z . Тогда существуют x 1 , x 2 ∈ X и y 1 , y 2 ∈ Y такие, что x 2 = x 1 z и y 2 = z y 1 . Отсюда следует, что x 2 y 1 = x 1 z y 1 =X−1X∩YY−1 z x1,x2∈X y1,y2∈Y x2=x1z y2=zy1 x2y1=x1zy1=x1y2 XY
источник