Na ciência da computação teórica , e em particular na teoria dos autômatos , um autômato linear limitado (em inglês linear bounded automaton , abreviado como LBA ) é uma máquina de Turing não determinística que usa apenas uma porção contígua da faixa de tamanho linear na entrada Tamanho.
Um autômato linearmente limitado satisfaz as três condições a seguir:
Quanto às máquinas de Turing , um autômato linearmente limitado tem uma faixa composta de caixas que provavelmente contém um símbolo retirado de um conjunto finito chamado alfabeto , uma cabeça pode ler o conteúdo de uma caixa e escrever nela e pode ser movida por 'um célula de cada vez e, finalmente, tem um número finito de estados.
Ao contrário de uma máquina de Turing , onde se presume que a fita tem comprimento potencialmente infinito, em um autômato linearmente limitado, apenas uma parte contígua da fita, cujo comprimento é uma função linear do comprimento dos dados, é acessível pelo cabeçote de leitura e gravação. Este segmento é delimitado pelas caixas contendo os marcadores finais.
Autômatos linearmente limitados reconhecem exatamente a classe de linguagens contextuais . Para mostrar que uma linguagem contextual é reconhecida por um autômato linearmente limitado, observamos que em uma gramática contextual , uma etapa de uma derivação sempre alonga a palavra produzida. Portanto, se tentarmos reduzir uma palavra a um axioma, cada passo equivalerá a encurtar a palavra. É por isso que basta uma memória limitada.
O argumento, na outra direção, é um pouco mais longo.
Em 1960 , John Myhill introduziu um modelo de um autômato agora chamado de autômato determinístico linearmente limitado . Pouco depois, Lawrence Landweber prova que as linguagens reconhecidas por autômatos determinísticos linearmente limitados são contextuais. Em 1964, Sige-Yuki Kuroda introduziu o modelo mais geral de autômato linearmente limitado (não determinístico) como descrito acima e provou que eles aceitam exatamente as linguagens contextuais.
Em seu artigo seminal, Kuroda apresenta dois problemas de pesquisa que se tornaram famosos sob o nome inglês de problemas LBA .
Kuroda já percebeu que uma resposta negativa para o segundo problema teria resultado em uma resposta negativa para o primeiro. Mas, na verdade, o segundo problema tem uma resposta positiva. Isso é uma consequência do teorema de Immerman-Szelepcsényi que liga as classes NSPACE e co-NSPACE. Este resultado, provado independentemente por Neil Immerman e Róbert Szelepcsényi em 1987 , rendeu-lhes o Prêmio Gödel em 1995 . Quanto ao primeiro problema, em 2010 ele ainda está aberto.