Que classe de idiomas é reconhecida pelos autômatos de estados finitos com

10

Um DFA ou NFA lê uma sequência de entrada com uma única cabeça, movendo-se da esquerda para a direita. Parece natural pensar em máquinas de estado finito que possuem várias cabeças , cada uma das quais se move pela entrada da esquerda para a direita, mas não necessariamente no mesmo local da entrada que as outras.

Vamos definir uma máquina de estados finitos com k cabeças da seguinte maneira:

Um NFA de cabeça k é uma tupla (Q,Σ,Δ,q0,F) , em que:

  • Como de costume, Q é um conjunto finito de estados, Σ é um alfabeto finito, q0 é um estado inicial e F é um conjunto de estados aceitantes. Deixe Σε:=Σ∪{ε} denotar o conjunto de caracteres, incluindo a sequência vazia.

  • Δ⊆Q×(Σε)k×Q é a relação de transição: uma transição(p,(σ1,σ2,…,σk),q) significa que, se a máquina está no estado dep , pode ler em(σ1,σ2,…,σk) modo queσi seja o próximo caractere para a cabeçai (ouε se essa cabeça não se mover) e depois vá para o estadoq .

Uma execução desse tipo de máquina (qualquer caminho que começa no estado inicial e termina no estado de aceitação) resulta em não uma sequência, mas em k strings diferentes (formadas pela concatenação dos caracteres ao longo da execução). Então dizemos que a execução é válida se as strings k forem idênticas.

O idioma da máquina é o conjunto de cadeias w modo que exista uma execução válida da máquina, onde as cadeias k produzidas ao longo dessa execução são iguais a w .

Pergunta: Qual é a classe de idiomas reconhecida por essas máquinas? Foi estudado?

{anbn∣n∈N}
23Exemplo de NFA de 2 cabeças

σ1/σ2(p,(σ1,σ2),q)

k

fl.formal-languages automata-theory regular-language nfa 6005
fonte
2
Olhando um pouco ao redor, vejo autômatos de várias cabeças sendo mencionados em arxiv.org/abs/0906.3051 : sua definição é sobre autômatos bidirecionais, mas eles também definem a variante unidirecional. Não há algo útil nesse artigo? ou em suas referências, por exemplo, sciencedirect.com/science/article/pii/S0304397509006288
a3nm 4/19/19
2
anbncn#
2
Obrigado pelas referências em papel - essa era apenas uma curiosidade ociosa e eu não havia conferido a literatura. Se ninguém mais o fizer, vou ler alguma literatura e responder com uma resposta que resuma os resultados conhecidos.
6005

Respostas:

5

Este modelo é um dos modelos padrão na teoria dos autômatos e foi examinado por alguns pesquisadores.

As referências dadas no primeiro comentário são muito bons pontos de partida.

Quando a cabeça é bidirecional, as classes de idiomas reconhecidas por esses modelos são idênticas às classes de espaço logarítmico. No entanto, quando o cabeçalho é unidirecional, pelo que sei, não temos uma caracterização exata semelhante, mas temos certos resultados incomparáveis ​​e algumas hierarquias baseadas no número de cabeçotes.

Se você estiver interessado, recomendo que você verifique também versões alternadas, probabilísticas e quânticas de autômatos de múltiplas cabeças. Esses modelos podem ser bastante interessantes, mesmo quando se usa um único cabeçote, pois o cálculo é dividido em caminhos diferentes e, em cada caminho, o cabeçote pode acessar diferentes partes das entradas.

Algumas referências genéricas:

Alternação

Computação probabilística

Computação probabilística e quântica

Modelos relacionados: autômatos com vários contadores e autômatos usando seixo.

Abuzer Yakaryilmaz
fonte