Autômato linearmente limitado

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, δ, S₀, F, V, <, >), e onde:

• Σ é o alfabeto de símbolos de entrada;
• S é o conjunto de estados possíveis, o qual é finito;
• δ é o programa ou função de transição
  • δ: S × (Σ ∪ V ∪ {<, >}) → 2^{S × (Σ ∪ V ∪ {<, >}) × {E, D}} a qual é uma função parcial;
• S₀ é o estado inicial da máquina, S0 ∈ S;
• F é o conjunto de estados finais, F ⊂ S;
• V é o alfabeto auxiliar (pode ser vazio);
• < é o símbolo especial marcador de início da fita;
• > é o símbolo especial marcador de fim da fita.

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.

Bibliografia

• COHEN, D. I. A. Introduction to Computer Theory. New York: John Wiley & Sons, 1997.
• MENEZES, P. B. Linguagens Formais e Autômatos. Porto Alegre: Sagra Luzzatto, 2005.
• VIEIRA, N. J. Introdução aos Fundamentos da Computação - Linguagens e Máquinas. São Paulo: Pioneira Thomson e Learning, 2006.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.
• John Myhill: Linearly Bounded Automata, WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, junho 1960.
• Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control 6(2): 131-136 (1963)
• Sige-Yuki Kuroda: Classes of languages and linear-bounded automata, Information and Control, 7(2): 207–223 (1964)

Ligações externas

• «SCTMF»  - Software para Criação e Teste de Modelos Formais.
• Linear Bounded Automata by Forbes D. Lewis
• Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
• Linear-Bounded Automata, part of Theory of Computation syllabus, by David Matuszek