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. $A$ $B$ $AB$ $w \in AB$ $w = ab$ $a \in A$ $b \in B$ $\{\varepsilon, \mathrm{a}\}$ $w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$ $\{\mathrm{a}\}$

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

algorithms formal-languages computability regular-languages ambiguity 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

10

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

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

para

aconteça em dois pontos diferentes". Eu não tenho certeza de como fazer isso à excepção de tomar o produto cruzado (?) De dois

DFAs e exclusão de toda a (

-terminal,

handwaving -terminal) produtos estados-eu estou, eu estou preocupado que a transição de

NFA para

DFA iria estragar a idéia de

A B

$AB$

A

$A$

B

$B$

A B

$AB$

A

$A$

A

$A$

A B

$AB$

A B

$AB$

A

$A$ -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 de , deixe $X$ $Y$ $A^*$ eu afirmam queé inequívoca se e apenas se o idiomaestá vazia.

\begin{aligned} X^{- 1} Y & = {u \in A^{*} ∣ there exists x \in X such that x u \in Y} \\ Y X^{- 1} & = {u \in A^{*} ∣ there exists x \in X such that u x \in Y} \end{aligned}

$\begin{align} X^{-1}Y &= \{u \in A^* \mid \text{there exists $x \in X$ such that $xu \in Y$} \} \\ YX^{-1} &= \{u \in A^* \mid \text{there exists $x \in X$ such that $ux \in Y$} \} \end{align}$

X Y

$XY$

X^{- 1} X \cap Y Y^{- 1} \cap A^{+}

$X^{-1}X \cap YY^{-1} \cap A^+$

Prova . Suponha que seja ambíguo. Em seguida, existe uma palavra que tem dois decomposições sobre , dizer , em que e . Sem perda de generalidade, podemos assumir que é um prefixo de , ou seja, $XY$ $u$ $XY$ $u = x_1y_2 = x_2y_1$ $x_1, x_2 \in X$ $y_1, y_2 \in Y$ $x_1$ $x_2$ para alguns . Segue que , de onde . Assim . $x_2 = x_1z$ $z \in A^+$ $u = x_1y_2 = x_1zy_1$ $y_2 = zy_1$ $z \in X^{-1}X \cap YY^{-1}$

Suponha agora que contenha alguma palavra não vazia . Então existem e tal que e . Segue que $X^{-1}X \cap YY^{-1}$ $z$ $x_1, x_2 \in X$ $y_1, y_2 \in Y$ $x_2 = x_1z$ $y_2 = zy_1$ e, portanto, o produto é ambíguo. $x_2y_1 = x_1zy_1 = x_1y_2$ $XY$

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

J.-E. PIN
fonte

z

$z$

Opa. Eu atualizo.

J.-E.

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

Respostas: