Existem autômatos não finitos?

35

Na teoria dos autômatos, todos nós lemos autômatos como autômatos finitos, desde o início. O que eu quero saber é: por que os autômatos são finitos? Para ser claro, o que é um autômato finito - o alfabeto, a linguagem, as seqüências de caracteres feitas com expressões regulares ou o quê? E há (em teoria) algum autômato não finito?

parvin
fonte
11
Certamente não a linguagem ou as "cordas feitas com expressões regulares"; muitas expressões regulares simples coincidir com um número infinito de strings (mas eles podem ser reconhecidos por um autômato finito.)
alexis
Eu fiz uma pergunta com uma pergunta em mente: cs.stackexchange.com/questions/55864/…
Words Like Jared

Respostas:

34

Todos os modelos de autômatos que você normalmente encontra são representados finitamente; caso contrário, haveria inúmeras, o que significa que elas não são capturadas pelos modelos completos de Turing. Ou, no pensamento de CS, eles seriam inúteis¹.

"Autômatos finitos" são chamados finitos porque eles só têm um conjunto finito de configurações (a sequência de entrada de lado). Os autômatos de empilhamento, por exemplo, têm uma pilha que pode ter conteúdo arbitrário - existem infinitas configurações possíveis.


Nota bene: As configurações de PDAs ainda são finitamente representadas! De fato, qualquer modelo computacional que se enquadre na computabilidade de Turing deve ter configurações finamente representáveis, caso contrário, as TMs não seriam capazes de simulá-las.


  1. Eu conscientemente desconsidero a hipercomputação aqui para o propósito desta pergunta.
Rafael
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Raphael
32

O nome completo é "autômato de estado finito ". A parte crucial é que o estado do autômato pode ser totalmente caracterizado por um elemento de algum conjunto finito de estados discretos. Isso significa que se o estado (relevante) do autômato envolve uma variável com valor real, há um número infinito de estados potenciais (deixando de lado a finitude das representações de ponto flutuante), e o autômato não é finito.

Isso pode nunca acontecer na ciência da computação teórica, mas não é muito exótico no domínio da modelagem de seqüências de números reais. Modelos de Markov ocultos podem ser usados ​​para modelar uma sequência numérica como a saída de um sistema probabilístico que consiste em um filtro de saída para cada estado de um modelo Markov (discreto, finito) com estados não observáveis. Os filtros calculam a próxima saída com valor real de um vetor das saídas anteriores (modelo "autoregressivo"), mas o modelo subjacente de Markov é finito, pois suas probabilidades de transição dependem apenas do estado atual de Markov.

No entanto, este artigo ( texto completo ) desenvolve uma variação em que as probabilidades de transição também dependem do vetor de número real de saídas anteriores. O estado desse sistema é a combinação de um estado Markov discreto e uma tupla de números reais ("modelo Markov de estado misto"); portanto, ele pode estar em um número infinito de estados diferentes.

Em resumo, autômatos não finitos são teoricamente bem definidos e, ocasionalmente, até encontrados.

alexis
fonte
11
Divulgação completa: Sou um dos autores do artigo mencionado. Eu não tenho certeza se isso é considerado divulgação adequada ou auto-promoção irrelevante ...
alexis
6
Eu acho perfeitamente bom fazer referência ao próprio trabalho, quando apropriado - se você é um dos principais especialistas em um tópico, estamos felizes em tê-lo! - e uma divulgação clara como a sua é suficiente. Obrigado!
Raphael
Autômatos de estado finito não incluem autômatos de empilhamento, certo? Existe uma razão específica para estados com números reais? Não tenho certeza se estou faltando alguma coisa aqui sobre por que esse exemplo óbvio não funcionaria ou se você simplesmente escolheu um exemplo incomum.
Mehrdad
11
Acho que ele está tentando perguntar por que você não usou um FSA não convencional mais como um autômato de pushdown em vez de pular para algo como variáveis ​​de estado com valor real.
User2357112 suporta Monica
11
Bem, principalmente porque esse é o exemplo em que pensei! Mas também o "estado" de um modelo de Markov de estado misto consiste em um número fixo de parâmetros, mas ainda há um número infinito de estados (definido como posição atual + probabilidades de transição) porque alguns dos parâmetros são números reais (mas afetam as transições, não apenas a saída). No caso do PDA, a não finitude vem do tamanho ilimitado da pilha; mas ainda há apenas um número finito de regras, que são de comprimento finito; portanto, em um único passo, há apenas um número finito de bebedores possíveis.
Alexis12 /
19

Em um autômato finito, há um pouco de finitude: o número de estados, o tamanho do alfabeto subjacente e os comprimentos das strings aceitas pela máquina.

Você certamente pode relaxar a condição de finitude neles permitindo, digamos, que a máquina tenha infinitos estados, mas se o fizer, a máquina resultante se tornará desinteressante, no sentido de que essas máquinas podem ser projetadas para aceitar qualquer idioma.

Rick Decker
fonte
E se for apenas o alfabeto que é infinito? e se estivermos trabalhando com uma expressão regular em números naturais, por exemplo? isso é possível?
parvin
8
Se o autômato for finito, mas o alfabeto for infinito, o autômato terá um número finito de transições para fora de cada estado. Qualquer caractere não associado a uma das transições não será reconhecido pelo autômato. Como resultado, você pode substituir o alfabeto infinito por um alfabeto finito contendo apenas os caracteres que aparecem nas transições do autômato, e o autômato ainda aceitaria exatamente o mesmo idioma.
Kevin - Restabelece Monica
3
@parvin Na verdade não. Você precisaria ter um número infinito de transições entre seus (número finito de) estados - o que você ainda não pode representar. Se você procurar predicados (como "todas as entradas pares vão de A a B, todas as entradas ímpares vão de A a C"), basicamente divide seu alfabeto em um número finito de classes de equivalência.
Bergi
@ Kevin, isso depende de como você define "número finito de transições". Considere um FSA comum (finito), com o próximo estado escolhido de acordo com qualquer partição finita dos números naturais: por exemplo, pelo restante da divisão por 7. Ou considere uma situação semelhante envolvendo números reais. O diagrama de estados é totalmente finito, mas está bem definido em um alfabeto infinito.
Alexis
@Parvin, eu diria que a resposta é "sim" (veja meu comentário anterior).
Alexis
10

De fato, na teoria dos autômatos (que se afasta muito das origens de Kleene, Rabin e Scott), existem muitas formas de autômatos que não são finitas. Isso surge por várias razões.

Os autômatos de empilhamento , por exemplo, são autômatos com um conjunto infinito de configurações (eles têm um número finito de estados, mas a realidade é que esses devem ser considerados como 'autômatos infinitos').

Na mesma linha, existem outros exemplos de autômatos infinitos para os quais o espaço de estados é infinito, mas com muita estrutura. Por exemplo, considera-se a classe de autômatos que têm como espaço de estado um espaço vetorial (dimensão finita) e como funções de transição mapas lineares (mais algumas coisas iniciais e finais). Estes são conhecidos como autômatos ponderados sobre um campo base (devido a Schützenberger em 61). Estes podem ser minimizados e testados quanto à igualdade. Outros exemplos incluem autômatos de registro (esses autômatos têm um conjunto finito de registros e funcionam com um alfabeto infinito: eles podem comparar letras com registros e armazenar letras em registros) e a forma mais moderna de autômatos nominais(que têm a mesma expressividade, mas têm melhores fundamentos e propriedades). O vazio de tais autômatos é decidível.

UMAumavocêvocêuma, e um estado está aceitando se pertencer a L). Há também um objeto final (que possui como idioma dos estados!). A existência desses dois objetos é uma maneira de explicar em alto nível por que os autômatos determinísticos podem ser minimizados e estão intimamente ligados à congruência Myhill-Nerode.

Para concluir, existem autômatos infinitos, mas os modelos que são estudados pela primeira vez em uma palestra são sempre os de estado finito.

Thomas Colcombet
fonte
2

Eu acho que a pergunta está assumindo a conclusão de que não há autômatos de estados infinitos quando existem, eles simplesmente não valem a pena ser trazidos à tona.

Na teoria dos autômatos, existe uma hierarquia de poderes de diferentes modelos virtuais. O que eu aprendi tinha 4 (que eu lembro, já faz algum tempo), o que eu encontrei na Wikipedia tem 5. O mais fraco nos autômatos de estados finitos e o mais forte são as máquinas de Turing. Existe um conceito de um nível mais poderoso do que as máquinas de Turing que é chamado livremente de hipercomputação. Muitas descrições diferentes de máquinas virtuais se enquadram em um desses níveis. As máquinas de Turing são especialmente conhecidas por vários modelos, todos com o mesmo nível de potência computacional.

Um autômato de estado infinito, pelo menos um formalmente definido, cairá em um desses níveis. Pode haver algo um pouco interessante em mostrar como uma certa definição rigorosa de um autômato de estado infinito se encaixa em um desses níveis, mas fora isso, não seria de muita utilidade, uma vez que existem máquinas virtuais muito mais estudadas que representam cada nível . É semelhante à forma como não há muito interesse em um bilhão de máquinas de Turing, pois não seria mais poderoso que uma única máquina de Turing, mas mais complicado de lidar.

Agora, se você encontrar um autômato de estado infinito que não seja equivalente a um nível existente da hierarquia, isso poderá ser interessante. Mas sem isso, os autômatos de estados infinitos já são capturados dentro da hierarquia existente e, dadas as complicações adicionais de lidar com o infinito, apenas evitamos da mesma maneira que evitamos qualquer modelo de máquina de Turing excessivamente complicado.

Lawtonfogle
fonte
2

A versão (ingênua) infinita da máquina determinista de estados finitos é muito poderosa . Uma coisa dessas seria capaz de "memorizar" qualquer idioma, de modo que não há muito a ser aprendido considerando-os.

Por exemplo, sobre um alfabeto binário, considere um autômato na forma de uma árvore binária completa de altura infinita. Cada string possível que você poderia considerar como entrada corresponde exclusivamente a um nó da árvore, para que você possa construir uma decisão para qualquer idioma simplesmente fazendo com que os nós correspondentes aceitem estados.


fonte