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

9

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:

×abcaaacbcabcbca

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 = aabc
a × ( b × c ) = a × b = a(a×b)×c=a×c=c
a×(b×c)=a×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?

Sr. Ariel
fonte

Respostas:

6

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 cAqa,qb,qc

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

ATabcaacbbaacccba

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 TA(abc)cAT(cba)aAT

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 }ATATRac{a,c}

ATRabcaabbcbcaccabababbcacbccacabcacabcabbcabcabcabcabc

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 Rum , um c Uma Um t R1 , 1 um , um um b , b bAATRA×ATRATA×ATRa,acAATR1,1a,aab,bb

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 a,aa,ab,bc

25 = 3 8 + 1 10 = 3 3 + 1A×ATR 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=38+110=33+1

David Lewis
fonte
Obrigado, realmente me ajudou a sua resposta para entender a idéia por trás do não determinismo e o "reverso" de um autômato. Eu estava tendo problemas para entender esses conceitos usando o livro de Hopcroft, agora estou usando o livro de Sipser "Introdução à teoria da computação", que é realmente bom.
Sr. Ariel
Considere a entrada . se move para após a entrada , em seguida, para na entrada , de modo que não é aceito, mas deve ser? 1 , 1 b , b b c , um b umba1,1b,bbc,aba
cemulate
8

L L R L() 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.LLRL

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 aL R a ) ( L bL R b ) ( L cL R c ) . ( )La,Lb,Lca,b,c

(LaLaR)(LbLbR)(LcLcR).
()

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 a()LaRa

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 bbbbx=ax=bcaab

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

Yuval Filmus
fonte
Ótima maneira de provar isso com a fórmula - voto a favor por isso. Quanto à idéia alternativa de "adivinhação e verificação não determinística", isso geralmente é bom para uma prova, mas é bastante difícil de ser realizado, conforme o problema o solicitar. Acho que há muitos detalhes ausentes aqui, como acompanhar a string do back-end.
David Lewis
@ David, os detalhes estão faltando de propósito.
Yuval Filmus
@Yuval - ele não disse que era lição de casa - confiamos nas pessoas aqui, correto? Eu também acho que essa prova de existência resultará em uma máquina bastante grande, provavelmente muito maior que o necessário.
David Lewis
@ David David: Gilles deu uma resposta mais completa, que mostra que a NFA não é realmente muito grande; o não determinismo faz isso por você. O DFA correspondente pode ser enorme, no entanto.
Raphael
@MohamedAbbas Talvez eu não esteja planejando verificar.
Yuval Filmus
6

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 . xy=z{a ,b ,c }1 1xyzxy=z{a,b,c}1 xx x1xxxxx

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, .xyxyxxyxyxyyx

Adicione um nó desconectado por causa da palavra vazia. Todos os nós são iniciais.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 .(x1,x2)y(z1,z2)x1yz1x2yz2(1,x)(x,x)x

Gilles 'SO- parar de ser mau'
fonte
Estou com um pouco de dificuldade para entender isso. Você não precisa verificar se leva a um conjunto de estados finitos? IAC, não é tão simples como "reverter tudo", pois você ainda precisa consumir da esquerda para a direita, mas multiplicar da direita para a esquerda, e não tenho certeza de que você tenha feito isso. xyyx
David Lewis
@DavidLewis O conjunto de estados é finito, eu o defini como . Inverti a ordem da multiplicação (exceto mais erros de digitação). {overleftarrowa,b,b,1}
Gilles 'SO- stop be evil'
5

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 baabcab
    • Adivinhe : Como o segundo símbolo é , o último símbolo deve ter sido . b babb
      • (Adivinhe :) É , então não aceite.cbc
    • Adivinha : Como o segundo símbolo é , o último símbolo deve ter sido . b cbbc
      • (Adivinhe :) É realmente , então aceitamos.ccc
  • Adivinha : Como o primeiro símbolo é , isso não é possível, portanto não aceite.aba
  • Adivinhe : Como o primeiro símbolo é , o produto rl de deve ter sidoa b c ccabcc
    • (Adivinhe :) Como o segundo símbolo é , o último símbolo deve ter sidob acba
      • (Adivinhe :) É , então não aceite.cac

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).

Rafael
fonte
A idéia de adivinhar uma string era estranha para mim, mas tenho lido o livro de Sipser e acho que é uma abordagem melhor para iniciantes como eu na teoria da computação.
Sr. Ariel
Pense em adivinhar como bifurcação com entrada assumida. Mas é preciso ter cuidado com as estratégias de adivinhação - garanta que todo o armazenamento necessário para adivinhação seja delimitado uniformemente para todos os threads bifurcados, caso contrário você não terá mais um autômato de estado finito . Além disso, é necessário um limite uniforme para o número de threads bifurcados ativos. Eu acho que a descrição de Raphael aqui funciona, mas precisa ser mencionada pelo menos.
David Lewis