Autômato de Büchi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


NoFonti.svg
Este artigo ou se(c)ção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde abril de 2013). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em ciência da computação e teoria dos autômatos, um Autômato de Büchi é um tipo de autômato ω, que estende um autómato finito para entradas infinitas. Ele aceita como entrada uma sequência infinita sse existe uma execução do autômato que visita (pelo menos) um dos estados finais infinitas vezes. Autômato de Büchi reconhece a linguagem Omega-regular, a versão da palavra infinita das linguagens regulares. Foi assim denominada por causa do matemático suíço Julius Richard Büchi que inventou esse tipo de autômato em 1962.[1]

Autômatos de Büchi são frequentemente utilizados em verificação de modelos como uma versão da teoria dos autômatos de uma fórmula em lógica temporal linear.

Definição formal[editar | editar código-fonte]

Formalmente, um Autômato de Büchi determinístico é uma tupla A = (Q,S,d,q0,F) que consiste nos seguintes componentes:

  • Q é um conjunto finito. Os elementos de Q são chamados estados de A.
  • S é um conjunto finito chamado alfabeto de A.
  • d: Q × S ? Q é uma função, chamada de função de transição de A.
  • q0 é um elemento de Q, chamado estado inicial.
  • FQ é o estado de aceitação. A aceita exatamente aquelas execuções em que pelo menos um dos estados infinitos frequentes ocorrem em  F.

No autômato de Büchi não-determinístico, a função de transição δ é substituída com uma relação de transição Δ que retorna um conjunto e estados. Geralmente, o autômato de Büchi refere-se ao autômato de Büchi não-determinístico.

Para um formalismo mais abrangente, veja também autômato ω.

Propriedades de fechamento[editar | editar código-fonte]

O conjunto dos autômatos de Büchi é fechado em relação a algumas das seguintes operações.

Seja A=(QA,Σ,ΔA,IA,FA) e B=(QB,Σ,ΔB,IB,FB) autômatos de Büchi e C=(QC,Σ,ΔC,IC,FC) seja um autômato finito.

  • União: Existe um autômato de Büchi que reconhece L(A)∪L(B).
Prova: Se nós assumirmos, w.l.o.g., QAQB é vazio então L(A)∪L(B) é reconhecido pelo autômato de Büchi (QAQB, Σ, ΔA∪ΔBIAIBFAFB).
  • Intersecção: Existe um autômato de Büchi que reconhece a linguagem L(A)∩L(B).
Prova: O autômato de Büchi A'=(Q',Σ,Δ',I',F') reconhece L(A)∩L(B), onde
  • Q' = QA × QB × {1,2}
  • Δ' = Δ1 ∪ Δ2
    • Δ1 = {( (qA,qB,1), a, (q'A,q'B,i) ) | (qA,a,q'A)∈ΔA e(qB,a,q'B)∈ΔB e se qA∈FA então i=2 ou então i=1 }
    • Δ2 = {( (qA,qB,2), a, (q'A,q'B,i) ) | (qA,a,q'A)∈ΔA e (qB,a,q'B)∈ΔB e se qB∈FB então i=1 ou então i=2 }
  • I' = IA × IB × {1}
  • F' = { (qA,qB,2) | qB∈FB }
Por construção, r'=(qA0,qB0,i0),(qA1,qB1,i1),... é uma execução do autômato A' numa cadeia de entrada w sse rA=qA0,qA1,... é executado A emw e rB=qB0,qB1,... é executado B em w. rA aceita e rB aceita sse r' é a concatenação de uma séria infinita de segmentos finitos de 1-estados(estados com um terceiro componente 1) e 2-estados(estados com um terceiro componente 2) alternativamente. Não existe uma série de segmentos de r' sse r' aceita por A'.
  • Concatenação: Existe um autômato de Büchi que reconhece a linguagem L(C)⋅L(A).
Prova: Se assumirmos, w.l.o.g., QCQA é vazio, então autômato de Büchin A'=(QC∪QA,Σ,Δ',I',FA) reconhece L(C)⋅L(A), onde
  • Δ' = ΔA ∪ ΔC ∪ { (q,a,q') | q'∈IA e  ∃f∈FC. (q,a,f)∈ΔC }
  • se IC∩FC é vazio, então I' = IC caso contrário I' = IC ∪ IA
  • Fechamento-ω: Se L(C) não contém a cadeia vazia então existe um autômato de Büchi que reconhece a linguagem (C)ω.
Prova: O autômato de Büchi que reconhece L(C)ω é construído em duas etapas. Primeiro, nós construímos um autômato finito A' tal que A' também reconhece L(C) mas não há transições de entrada para os estados iniciais de A'. Então, A'=(QC ∪ {qnovo},Σ,Δ',{qnovo},FC), onde Δ' = ΔC ∪ { (qnovo,a,q') | ∃q∈IC. (q,a,q')∈ΔC}. Note que L(C)=L(A') porque L(C) não contém a cadeia vazia. Segundo, nós iremos construir o autômato de Büchi A" que reconhece L(C)ω pela adição de um loop de volta ao estado inicial de A'. Então, A"=(QC ∪ {qnovo},Σ,Δ",{qnovo},{qnovo}), onde Δ" = Δ' ∪ { (q,a,qnovo) | ∃q'∈FC. (q,a,q')∈Δ'}.
  • Complemento:Existe um autômato de Büchi que reconhece a linguagem Σ*/L(A).
Prova: A prova é apresentada aqui.

Linguagens Reconhecíveis[editar | editar código-fonte]

O autômato de Büchi reconhece as linguagens ω-regulares. Utilizando a definição de linguagem ω-regular e as propriedades de fechamento do autômato de Büchi mostradas acima, pode ser facilmente demonstrado que um autômato de Büchi pode ser construído de tal forma a reconhecer qualquer linguagem ω-regular dada. Para mais, veja construção de uma linguagem w-regular por um autômato de Büchi.

Autômato de Büchi determinístico e não-determinístico
Um autômato de Büchi que reconhece (0+1)*0ω

A classe de autômatos de Büchi determinísticos não é suficiente para abranger todas as línguagens ω-regulares. Em particular, não existe um autômato de Büchi determinístico que reconheça a linguagem (0+1)*0ω (Qualquer palavra que possui um sufixo infinito consistindo apenas de 0's). Podemos demonstrar por contradição que nenhum autômato de Büchi determinístico como esse existe. Vamos supor A como um autômato de Büchi determinístico que reconhece (0+1)*0ω como o estado final F. A aceita 0ω. Então, A irá visitar algum estado F depois de ler alguns prefixos finitos de 0ω, digamos após a i0th letra. A também aceita a ω-cadeia 0i010ω. Portanto, para algum i1, após o prefixo 0i010i1 o autômato irá visitar algum estado em F. Continuando com esta construção da ω-palavra 0i010i110i2... é gerado, o que causa a visita de A em algum estado de F infinitas vezes e a cadeia não está em(0+1)*0ω. Contradição.

A classe de linguagens reconhecíveis por autômatos de Büchi determinísticos é caracterizada pelo seguinte lema.

Lema: Uma ω-linguagem é reconhecível por um autômato de Büchi determinístico sse ela é limite de alguma linguagem regular.
Prova: Qualquer autômato de Büchi determinístico A pode ser visto como um autômato finito determinístico A' e vice-versa, uma vez que ambos os tipos de autômato são definidos como 5-tuplas de mesmos componentes, apenas a interpretação de condição de aceitação é diferente. Iremos mostrar que L(A) é o limite de L(A'). Uma ω-cadeia é aceita por A sse ela irá forçar A a visitar os estados finais infinitas vezes. Sse, um número infinito de prefixos desta ω-cadeia irá ser aceita por A'. Assim, G(A) é uma linguagem limite de L(A').

Algoritmos[editar | editar código-fonte]

Verificação de modelos de sistemas de estados finitos podem muitas vezes ser traduzidos em várias operações de Autômatos de Büchi. Além das operações de fecho apresentadas acima, a seguir estão algumas operações úteis para as aplicações do Autômato de Büchi.

Determinização

Desde que os autômatos de Büchi determinísticos são estritamente menos expressivos do que os autômatos não-determinísticos, não pode haver um algoritmo para determinização do Autômato de Büchi. Mas o teorema de McNaughton e a construção de Safra fornecem algoritmos que podem traduzir um autômato de Büchi em um autômato de Muller determinístico ou um autômato de Rabin determinístico.

Verificação de vacuidade

A linguagem reconhecida por um autômato de Büchi não é vazia sse existe um estado final que acessível a partir do estado inicial, e encontra-se em um ciclo.

Um algoritmo eficiente que pode verificar o vazio de um autômato de Büchi:

  1. Considere o autômato como um grafo direcionado e decompô-lo em componentes fortemente conectados .
  2. Executar uma pesquisa (por exemplo,a busca em profundidade) para encontrar os componentes que são acessíveis a partir do estado inicial.
  3. Verificar se existe um componente fortemente ligado não trivial que seja acessível e contém um estado final.

Cada um dos passos deste algoritmo pode ser feito em tempo linear no tamanho autômato, portanto, o algoritmo é claramente ótimo.

Redução ao mínimo

O algoritmo para minimizar o autômato finito não-determinístico também minimiza corretamente um autômato de Büchi. O algoritmo não garante o mínimo autômato de Büchi. Note que algoritmos para minimizar o autômato finito determinístico não funciona mpara o autômato de Büchi determinístico.


Referências[editar | editar código-fonte]

  1. J.R. Büchi. Em um método de decisão na aritmética restrito de segunda ordem. In Proc. International Congress on Logic, Method, and Philosophy of Science. 1960, pages 1–12, Stanford, 1962. Stanford University Press.