Quando a concatenação de dois idiomas regulares é inequívoca?

16

Dadas as línguas e , digamos que sua concatenação seja inequívoca se, para todas as palavras , houver exatamente uma decomposição com e e ambígua caso contrário. (Não sei se existe um termo estabelecido para essa propriedade - coisa difícil de procurar!) Como um exemplo trivial, a concatenação de consigo mesma é ambígua ( ), mas a concatenação de consigo mesma é inequívoca.ABABwABw=abaAbB{ε,a}w=a=εa=aε{a}

Existe um algoritmo para decidir se a concatenação de duas linguagens regulares é inequívoca?

rstern
fonte
1
Gah, isso é totalmente um problema de calouro, não é? Honestamente, não tentei muito; Eu esperava que houvesse um algoritmo estabelecido para isso em algum lugar da literatura e não tivesse que reinventar a roda. Estou escrevendo software aqui; Eu fiz apenas alguns cursos de CS (há vários anos), então estou basicamente começando na Wikipedia. Sei que ninguém gosta de alguém que não quer trabalhar para obter a resposta, então, se houver um livro ou um trabalho ou algo que você possa me apontar, em vez de apenas me entregar um algoritmo, isso seria útil! Obrigado!
28915 rstern
Eu adicionei isso como um comentário, porque, bem, é um tópico relativamente estranho, mas talvez possa levar você a alguma ajuda. O Unicode Consortium possui alguns processos para determinar a semelhança entre os idiomas. Eu li um link muito informativo no site deles, mas por minha vida não consegui encontrá-lo hoje para fazer disso uma resposta. Se você tiver tempo para pesquisar isso, aqui está a página de perguntas mais frequentes unicode.org/faq
htm11h 30/07/2015

Respostas:

10

Dica: Dado AFDs para e B , construir um AFN que aceita palavras Um B possuindo pelo menos dois diferentes decomposições. O NFA mantém um registo de duas vias de NFA padrão para um B (formada pela junção AFDs para um e B com £ transições), assegurando que a passagem de uma para B acontece em dois pontos diferentes.ABABABABϵAB

Yuval Filmus
fonte
Obrigado pela dica! Então, se eu entendi, eu posso construir um NFA para palavras ambíguas em e, em seguida, testar se autômato para o vazio. A parte complicada parece ser "garantir que a mudança de A para B aconteça em dois pontos diferentes". Eu não tenho certeza de como fazer isso à excepção de tomar o produto cruzado (?) De dois Um B DFAs e exclusão de toda a ( A -terminal, A handwaving -terminal) produtos estados-eu estou, eu estou preocupado que a transição de A B NFA para A B DFA iria estragar a idéia de AABABABAAABABA-terminal. Parece, porém, ineficiente; existe um algoritmo conhecido adequado para software?
28915 rstern
Sim, não parece muito eficiente, embora sempre exista a opção de fazê-lo de maneira inteligente. Não conheço nenhum algoritmo específico para esse problema, mas um pode existir.
Yuval Filmus
7

Atualizado (graças a Yuval Filmus).

Dado dois idiomas e Y de A , deixe X - 1 YXYA eu afirmam queXYé inequívoca se e apenas se o idiomaX-1XYY-1Uma+está vazia.

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

Prova . Suponha que seja ambíguo. Em seguida, existe uma palavra de u que tem dois decomposições sobre X Y , dizer u = x 1 y 2 = x 2 y 1 , em que x 1 , x 2X e Y 1 , Y 2Y . Sem perda de generalidade, podemos assumir que x 1 é um prefixo de x 2 , ou seja, x 2 = xXYuXYu=x1y2=x2y1x1,x2Xy1,y2Yx1x2 para alguns z A + . Segue que u = x 1 y 2 = x 1 z y 1 , de onde y 2 = z y 1 . Assim z X - 1 X Y Y - 1 .x2=x1zzA+u=x1y2=x1zy1y2=zy1zX1XYY1

Suponha agora que contenha alguma palavra não vazia z . Então existem x 1 , x 2X e y 1 , y 2Y tal que x 2 = x 1 z e y 2 = z y 1 . Segue que x 2 y 1 = x 1 z y 1 =X1XYY1zx1,x2Xy1,y2Yx2=x1zy2=zy1 e, portanto, o produto X Y é ambíguo.x2y1=x1zy1=x1y2XY

Se e Y são regulares, então X - 1 X e Y Y - 1 são regulares e, portanto, X - 1 X Y Y - 1 também é regular (consulte a resposta de Yuval para um autômato que aceita esse idioma).XYX1XYY1X1XYY1

J.-E. PIN
fonte
z
Opa. Eu atualizo.
J.-E.