Autômato linearmente limitado

Aspeto mover para a barra lateral ocultar

Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto. Sua fita é limitada e, portanto, finita. Ele só consegue resolver problemas que usem uma quantidade de memória que possa caber dentro da fita usada para entrada. Se por acaso utilizarmos um alfabeto de fita maior que o alfabeto de entrada então teremos um incremento da memória disponível por até um fator constante, por isso se tivermos uma entrada de tamanho na quantidade de memória disponível será linear em relação a n. Apesar de suas restrições os ALLs são bastantes potentes, podemos citar que os decisores para o problema da aceitação de um AFD para uma dada entrada, para o problema da vacuidade de um dado AFD, para o problema da aceitação de uma gramática livre de contexto e para a vacuidade de uma dada gramática livre de contexto são todos ALLs.

O Autômato Linearmente Limitado é um formalismo reconhecedor não determinístico, o qual pode ser definido por uma óctupla (Σ, S, δ, S0, F, V, <, >), e onde:

O ALL possui uma fita de entrada a qual tem tamanho finito e é delimitada pelos símbolos <e >, possui também um cabeçote de Leitura/Escrita, o qual tem a posição inicial sempre na primeira célula a direita do símbolo á, sempre que o cabeçote lê um símbolo ele deve escrever outro na mesma célula e mover-se para esquerda ou para direita. Como tem caráter não determinístico os estados podem ter mais de uma saída com o mesmo símbolo, quando isso ocorre uma ‘cópia’ do ALL é criada e executada simultaneamente, a primeira ‘cópia’ que parar em um estado final é aceita, e as outras são excluídas. A transição é representada por (símbolo lido, símbolo a ser escrito, direção para qual o cabeçote de leitura/escrita deve ir).

Uma característica importante dos ALLs é que um ALL pode ter somente um número limitado de configurações dado que a entrada tem tamanho n.

Dado que a entrada tem tamanho n, seja M um ALL com "q" estados e "s" símbolos no alfabeto da fita então podemos dizer que existem exatamente "q*n*s^n" configurações distintas de M.

Não se sabe se a versão não determinística desta máquina aumenta ou não o poder computacional das Máquinas de Turing com Memória Limitada.

ALL e Linguagens sensíveis ao contexto

Autômatos linearmente limitados são aceitadores para a classe de linguagens sensíveis ao contexto. A única restrição colocada nas gramáticas para tais linguagens é que não há produção do que mapeia uma cadeia para uma cadeia mais curta. Assim, nenhuma derivação de uma cadeia em uma linguagem sensível ao contexto pode conter uma forma sentencial mais do que a cadeia em si. Uma vez que existe uma correspondência um-para-um entre autômatos linearmente limitados e tais gramáticas, não mais do que a fita ocupada pela cadeia original é necessária para a cadeia a ser reconhecida pelo autômato.

História

Em 1960, Myhill introduziu um modelo de autômato hoje conhecida como autômato linearmente limitado determinístico. Pouco depois, Landweber provou que as linguagens aceitas por um ALL determinístico são sempre sensíveis ao contexto. Em 1964, Kuroda introduziu o modelo mais geral (não determinístico) de autômatos linearmente limitados, e mostrou que as linguagens aceitas por eles são precisamente as linguagens sensível ao contexto.

Problemas ALL

Em seu artigo seminal, Kuroda afirmou também dois desafios de pesquisa, que posteriormente se tornaram notoriamente conhecidos como os "problemas ALL": O primeiro problema ALL é se a classe de linguagens aceitas pelo ALL é igual à classe de linguagens aceitas pelo ALL determinístico. Este problema pode ser formulado de forma sucinta na linguagem da teoria da complexidade computacional como:

Primeiro problema ALL: É verdade que NSPACE(O(n)) = DSPACE(O(n))?

O segundo problema ALL é se a classe de linguagens aceitas por um ALL é fechada sob complementação.

Segundo problema ALL: É verdade que NSPACE(O(n)) = co-NSPACE(O(n))?

Como já observado por Kuroda, uma resposta negativa ao segundo problema ALL implicaria uma resposta negativa ao primeiro problema. Mas o segundo problema ALL tem uma resposta afirmativa, o que está implicado pelo teorema Immerman-Szelepcsényi, provado apenas mais de 20 anos depois que o problema foi levantado. Ainda em 2011, o primeiro problema ALL permanece em aberto.

Teoria da computação

Referências

  1. ↑ a b c d e f g h Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to automata theory, languages, and computation. Internet Archive. : Reading, Mass. : Addison-Wesley 
  2. ↑ a b c d e f g h Kuroda, S. -Y. (1 de junho de 1964). «Classes of languages and linear-bounded automata». Information and Control (2): 207–223. ISSN 0019-9958. doi:10.1016/S0019-9958(64)90120-2. Consultado em 1 de janeiro de 2024 
  3. ↑ a b c d e f g h «Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak». theory.cs.princeton.edu. Consultado em 1 de janeiro de 2024 
  4. ↑ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata (em inglês). : John Benjamins Publishing 

Bibliografia

Ligações externas