Palavras que têm o mesmo produto associativo direito e esquerdo

Comecei a estudar autômatos não determinísticos usando o livro de Hopcroft e Ullman . Estou preso em um problema que achei muito interessante:

Forneça um autômato finito não determinístico, aceitando todas as cadeias que tenham o mesmo valor quando avaliadas da esquerda para a direita e da direita para a esquerda, multiplicando de acordo com a tabela a seguir:

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

Portanto, se temos a string , o produto da esquerda para a direita é (a \ times b) \ times c = a \ times c = c e o produto da direita para a esquerda é a \ times (b \ times c) = a \ times b = a$abc$
a × ( b × c ) = a × b = $(a \times b) \times c=a \times c=c$
$a \times (b \times c)=a \times b=a$

Portanto, $abc$ não deve ser aceitável para os autômatos. Para mim, é óbvio que qualquer string $aa^*$ ou $bb^*$ ou $cc^*$ é uma string aceitável (sua avaliação direita e esquerda funciona nas mesmas strings parciais). É fácil fornecer um NFA que descreva a avaliação da esquerda para a direita, mas o problema é que, se a máquina tentar calcular a avaliação da direita para a esquerda , acho que precisa saber o comprimento da string (é necessária uma memória infinita).

Então, como um autômato não determinístico pode avaliar da direita para a esquerda para comparar com a avaliação da esquerda para a direita?

O primeiro truque aqui é pensar na tabela de multiplicação como a tabela de transição de um autômato com cada estado representando uma letra em sua tabela de multiplicação, mas ainda não se preocupando com a aceitação. Portanto, as letras à esquerda e no corpo da tabela são na verdade estados - seria mais preciso escrevê-las como , mas não vou. As letras na parte superior são entradas.q a , q b , q $A$$q_a, q_b, q_c$

Em seguida, construa o autômato (" " para transposição) para multiplicação reversa , transpondo : T $A_T$$T$$A$

$\qquad \displaystyle\begin{array}{c|ccc} A_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

Portanto, leva você ao estado , e da mesma forma passa para o estado de , como você observa.c A T ( c b a ) a A $A(abc)$$c$$A_T(cba)$$a$$A_T$

No entanto, assume que você está indo da direita para a esquerda e ainda queremos ir da esquerda para a direita. Portanto, o segundo truque é reverter o autômato (e não a multiplicação, que nos faria voltar quando começamos), revertendo todas as setas, o que leva a um autômato não determinístico fornecido pela tabela de transição abaixo, com subconjuntos indicados por letras concatenadas para manter o frango coçando, então é realmente . (espero que eu tenha conseguido tudo certo - parece funcionar).A T R a c { a , c $A_T$$A_{TR}$$ac$$\{a,c\}$

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

Você pode interpretar isso como um autômato não determinístico com apenas as três linhas acima da linha ou uma versão determinada com todas as 8 linhas.

Finalmente, a máquina para resolver o problema é o autômato produto cruzado do original e , que é para executar o comportamento intersecção dos dois autômatos (não precisamos qualquer Mais). possui estados que são pares como . A função de transição executa e independente. Um único estado inicial entra em na entrada , em na entrada , etc. Um T R A × A T R A T A × A T R ⟨ um , um c ⟩ Uma Um t R ⟨ 1 , 1 ⟩ ⟨ um , um ⟩ um ⟨ b , b ⟩ $A$$A_{TR}$$A \times A_{TR}$$A_T$$A \times A_{TR}$$\langle a,ac\rangle$$A$$A_{TR}$$\langle 1,1 \rangle$$\langle a,a \rangle$$a$$\langle b,b \rangle$$b$

Os estados de aceitação na versão não determinística são etc. Na versão determinística, os estados de aceitação são pares nos quais o primeiro componente está segundo conjunto de componentes, como ou .∈ ⟨ um , um ⟩ ⟨ b , b c $\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

25 = 3 ⋅ 8 + 1 10 = 3 ⋅ 3 + $A \times A_{TR}$ aumentado e determinado como mostrado tem estados, então me perdoe se eu não o escrever em detalhes. Mas a versão não determinística possui apenas estados.$25=3\cdot 8+1$$10=3\cdot 3+1$

L L R$(\ast)$ Se é um idioma regular, então , o idioma que consiste no inverso de todas as palavras em , também é regular. Tome isso como um exercício.$L$$L^R$$L$

Como isso nos ajuda a resolver o problema? Seja os idiomas que consistem em todas as cadeias que são avaliadas para ao avaliar da esquerda para a direita. O idioma em que você está interessado é Isso mostra que, se você souber como provar , poderá criar um NFA para o idioma em questão. a , b , c ( L a ∩ L R a ) ∪ ( L b ∩ L R b ) ∪ ( L c ∩ L R c ) . ( ∗ $L_a,L_b,L_c$$a,b,c$

De fato, se você usar a idéia da prova de , provavelmente poderá prosseguir e construir o autômato. Então, vamos considerar isso. Em particular, vamos tentar construir um NFA para , o idioma de todas as strings que são avaliadas como quando avaliadas da direita para a esquerda.L R a$(\ast)$$L_a^R$$a$

A ideia é essa. Suponha que a primeira letra que você vê seja . Em seguida, o restante da string deve ser avaliado como (já que implica ). Raciocínio semelhante se aplica quando a primeira letra é . Quando a primeira letra é , no entanto, o restante pode ser avaliado como ou ou ser nulo. Com um NFA, podemos adivinhar (e depois verificar nosso palpite).b b x = a x = b c a a $b$$b$$bx = a$$x = b$$c$$a$$a$$b$

Essa dica deve lhe dar o suficiente para pensar e, esperançosamente, resolver o problema.

Fofa.

Primeiro, crie um autômato que calcule o produto da esquerda para a direita. Fácil! Coloque uma transição sempre que . Existem três estados representando os três produtos possíveis. Comece em um quarto estado com para todos os . O estado final é se e somente se o produto da palavra de entrada da esquerda para a direita for . x⋅y=z{ → a , → b , → c } → 1 → $\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$$x \cdot y = z$$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$$\overrightarrow 1$ x → x$\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$$x$$\overrightarrow x$$x$

Agora vamos construir um autômato que calcula o produto da direita para a esquerda. Este será não determinístico. Como fazemos isso? Simples ... Para ir na outra direção, basta inverter tudo : as setas e a direção do produto.

Onde tínhamos antes de , agora : quando consumimos a palavra da esquerda para a direita, passamos de um produto para o fator da direita. Ou, em outras palavras, .$\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$← $\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$

Adicione um nó desconectado por causa da palavra vazia. Todos os nós são iniciais.$\overleftarrow 1$

Agora, precisamos calcular os dois caminhos juntos, para pegar o produto dos dois autômatos: iff e . Seja os quatro estados sejam iniciais e os quatro estados sejam finais. Uma palavra é reconhecida por esse autômato não determinístico se o produto da esquerda para a direita e o produto da direita para a esquerda forem iguais .$(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$$\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$$\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$$(\overrightarrow 1, \overleftarrow x)$$(\overrightarrow x, \overleftarrow x)$$x$

Parece que o seu principal problema está utilizando o não-determinismo, então deixe-me detalhar isso.

A idéia básica que os outros utilizam é ​​que uma máquina não determinística pode adivinhar o resultado final.

Vamos considerar o seu pequeno exemplo e a ideia de construção de Gilles. O autômato "computando" o produto da direita para a esquerda adivinha o resultado no início e o verifica . Portanto, existem três possibilidades:$abc$

• Adivinhe : Como o primeiro símbolo é , o produto rl de deve ter sido ou . a b c a $a$$a$$bc$$a$$b$
  • Adivinhe : Como o segundo símbolo é , o último símbolo deve ter sido . b $a$$b$$b$
    • (Adivinhe :) É , então não aceite.$b$$c$
  • Adivinha : Como o segundo símbolo é , o último símbolo deve ter sido . b $b$$b$$c$
    • (Adivinhe :) É realmente , então aceitamos.$c$$c$
• Adivinha : Como o primeiro símbolo é , isso não é possível, portanto não aceite.$b$$a$
• Adivinhe : Como o primeiro símbolo é , o produto rl de deve ter sidoa b c $c$$a$$bc$$c$
  • (Adivinhe :) Como o segundo símbolo é , o último símbolo deve ter sidob $c$$b$$a$
    • (Adivinhe :) É , então não aceite.$a$$c$

Como você pode ver, o NFA é capaz de adivinhar e verificar todos os cálculos possíveis de baixo para cima . Como o idioma aceito é definido como o conjunto de cadeias que é aceito por pelo menos uma execução , todas as execuções que não aceitam a entrada são ignoradas; o NFA "sempre adivinha certo".

Agora é fácil para este NFA lembrar sua primeira escolha até o final. Se aceitar, ele pode comparar o símbolo lembrado com o produto lr (deterministicamente) obtido em paralelo (como a interseção da linguagem se relaciona com a NFA certamente é abordada em Ullman / Hopcroft e em qualquer outro livro básico).