Idiomas aceitos por versões modificadas de autômatos finitos

16

Um autômato finito determinístico (DFA) é um modelo de máquina de estado capaz de aceitar todas e apenas linguagens regulares. Os DFAs podem ser (e geralmente são) definidos de tal maneira que cada estado deve fornecer alguma transição para todos os elementos do alfabeto de entrada; em outras palavras, a função de transição deve ser uma função (total).δ:Q×ΣQ

Imagine o que chamaremos de autômato finito duplamente determinístico (DDFA). É definido de maneira semelhante a um DFA, com duas exceções: primeiro, em vez da transição que leva de um estado para outro para cada símbolo de entrada possível, deve levar a dois estados distintos; segundo, para aceitar uma sequência, todos os caminhos em potencial devem satisfazer uma ou outra das seguintes condições:

  1. Todos os caminhos em potencial através do DDFA levam a um estado de aceitação (chamaremos isso de DDFA do tipo 1).
  2. Todos os caminhos em potencial pelo DDFA levam ao mesmo estado de aceitação (chamaremos isso de DDFA do tipo 2).

Agora, minha pergunta:

Quais idiomas os DDFAs do tipo 1 e do tipo 2 aceitam? Especificamente, , L (DDFA) = L (DFA) ou L (DDFA) \ subsetneq L (DFA) ? No caso de L (DDFA) \ neq L (DFA) , existe uma descrição fácil de L (DDFA) ?G ( D D F A ) = G ( D F A ) G ( D D F A ) G ( D F A ) G ( D D F A ) L ( D F A ) L ( D D F)eu(DFUMA)eu(DDFUMA)eu(DDFUMA)=eu(DFUMA)eu(DDFUMA)eu(DFUMA)eu(DDFUMA)eu(DFUMA)eu(DDFUMA)

As provas (ou pelo menos esboços moderadamente detalhados) são apreciadas, se não forem muito complicadas.

Patrick87
fonte

Respostas:

9

Isso combinado com a resposta de Alex fornece uma imagem completa.

eu(DDFUMA)eu(DFUMA) pode ser comprovado adaptando a construção usual do conjunto de potências com uma condição de estado final modificada. Na construção do conjunto de potência, estados são conjuntos de estados do autômato original. Geralmente, após executar a construção do conjunto de potências, um estado é final se um dos estados do conjunto for final no autômato original.

  • No DDFA do tipo 1, estados finais no autômato construído são os conjuntos em que todos os elementos são finais no autômato original.

  • No DDFA do tipo 2, estados finais são os conjuntos singleton dos estados finais do autômato original.

Nos dois casos, os autômatos resultantes são DFAs.

Agora, os 2DDFA de tipo podem expressar apenas os idiomas e , dependendo se o estado inicial está sendo aceito ou não. Isso ocorre porque as duas transições de um estado precisam ir para estados distintos, mas a aceitação só é possível se elas acabarem no mesmo estado.{ϵ}

Dave Clarke
fonte
7

Para começar a análise, posso dizer que para o tipo 1.eu(DFUMA)eu(DDFUMA)

Você pode fazer isso duplicando um DFA e adicionando arestas aos estados duplicados. Se um estado tiver uma transição para em , você fará uma transição de para em também. Além disso, tem uma transição para e em . Obviamente, isso significa que estaremos quase sempre nos estados e ao mesmo tempo (ou possivelmente apenas , inicialmente) e, portanto, reconheceremos o mesmo idioma.s 2 x s 1 s 2 x s 1 s 2 s 2 x s i s i s is1s2xs1s2xs1s2s2xsEusEusEu

Atualização: também temos para o tipo 2, pois não existe um DDFA do tipo 2 que reconheça o idioma . Se você tentar criar esse DDFA, terá um estado inicial e precisará de duas arestas de saída para os estados e em um , mas esses estados devem ser distintos e, portanto, os dois caminhos de aceitação terminam em diferentes aceitando estados.eu(DFUMA)eu(DDFUMA){uma}ss1s2uma

Juntamente com a resposta de Dave Clarke, isso fornece uma análise completa.

Alex ten Brink
fonte
Muito bom ver esse exemplo de contador para o tipo 2!
21812 Dave Clarke
@ Dave Clarke: obrigado. É um pouco de um exemplo bobo, mas funciona :)
Alex ten Brink
"Patológico" no lugar de "bobo".
21412 Dave Clarke
Bom trabalho, pessoal. Havia quatro coisas para verificar, e cada um de vocês tem duas. A menos que um de vocês se oponha, selecionarei @DaveClarke como a resposta, apenas porque ele tem menos reputação que Alex.
Patrick87
1
Em uma nota relacionada, você gostaria de elaborar os idiomas aceitos pelos DDFAs do tipo 2 ou devo fazer uma pergunta separada e criar um link para esta?
Patrick87