Когда конкатенация двух обычных языков однозначна?

16

Указанные языки и , скажем , что их конкатенация является однозначной , если для всех слов , существует ровно один разложение с и , и неоднозначном иначе. (Я не знаю, есть ли установленный термин для этого свойства - трудная вещь для поиска!) В качестве тривиального примера, конкатенация с самим собой неоднозначна ( ), но сцепление с самим собой однозначно.ABABwABw=abaAbB{ε,a}w=a=εa=aε{a}

Существует ли алгоритм для определения того, является ли объединение двух регулярных языков однозначным?

rstern
источник
1
Ага, это проблема первокурсника CS, не так ли? Честно говоря, я не очень старался; Я надеялся, что где-то в литературе есть установленный алгоритм для этого, и мне не придется изобретать велосипед. Я пишу программное обеспечение здесь; Я только взял несколько курсов CS (несколько лет назад), поэтому я в основном начинаю с Википедии. Я знаю, что никому не нравится кто-то, кто не хочет работать за их ответ, поэтому, если есть учебник, статья или что-то, на что вы могли бы указать мне, вместо того, чтобы просто передать мне алгоритм, это было бы полезно! Благодарность!
rstern
Я добавил это как комментарий, потому что, ну, это относительно не по теме, но, возможно, может привести вас к некоторой помощи. Консорциум Unicode имеет несколько процессов для определения общности языков. Я прочитал очень информативную ссылку на их сайте, но, судя по всему, не смог найти сегодня, чтобы вместо этого ответить. Если у вас есть время , чтобы исследовать это здесь их FAQ Страница unicode.org/faq
htm11h

Ответы:

10

Подсказка: учитывая DFA для и , создайте NFA, который принимает слова в имеющие как минимум два разных разложения. NFA отслеживает две копии стандартного NFA для (сформированных путем объединения DFA для и с переходами ), обеспечивая переключение с на в двух разных точках.AA B A B A B ϵ A BBABABABϵAB

Юваль Фильмус
источник
Спасибо за подсказку! Поэтому, если я понимаю, я могу построить NFA для неоднозначных слов в а затем проверить этот автомат на пустоту. Сложная часть, кажется, «гарантирует, что переключение с А на В происходит в двух разных точках». Я не уверен , как это сделать, кроме принимая декартово произведения (?) Два A B ДКИ и удаления всего ( терминальном, handwaving терминальном) продукта государство-я, я обеспокоен тем, что переход от A B NFA к A B DFA ввернул бы идею AABABABAAABABA-Терминал. Звучит, но неэффективно; Есть ли известный алгоритм, подходящий для программного обеспечения?
rstern
Да, это звучит не слишком эффективно, хотя всегда есть возможность сделать это разумно. Я не знаю ни одного конкретного алгоритма для этой проблемы, но он может существовать.
Юваль Фильмус
7

Обновлено (спасибо Yuval Filmus).

Для двух языков и Y в A пусть X - 1 YXYA Я утверждаючтоХYявляется однозначным тогда и только тогдакогдаязыкеХ-1XYY-1+пуст.

X1Y={uAthere exists xX such that xuY}YX1={uAthere exists xX such that uxY}
XYX1XYY1A+

Доказательство . Предположим, что неоднозначно. Тогда существует слово ¯u , который имеет два разложения над X Y , скажем , у = х 1 у 2 = х 2 у 1 , где х 1 , х 2Х и у 1 , у 2Y . Без ограничения общности можно считать, что x 1 является префиксом x 2 , то есть x 2 = xXYuXYu=x1y2=x2y1x1,x2Xy1,y2Yx1x2 для некоторого 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=x1zzA+u=x1y2=x1zy1y2=zy1zX1XYY1

Предположим теперь, что содержит некоторое непустое слово z . Тогда существуют x 1 , x 2X и y 1 , y 2Y такие, что x 2 = x 1 z и y 2 = z y 1 . Отсюда следует, что x 2 y 1 = x 1 z y 1 =X1XYY1zx1,x2Xy1,y2Yx2=x1zy2=zy1x2y1=x1zy1=x1y2XY

XYX1XYY1X1XYY1

J.-E. Штырь
источник
Что, если Z is the empty word?
Yuval Filmus
Ooops. I update.
J.-E. Pin