O tratamento de Linguagens Naturais requer o emprego de formalismos mais complexos que aqueles normalmente empregados para Linguagens Livre de Contexto. A maioria de tais formalismos são difíceis de serem utilizados, não práticos e sobretudo, associados a um desempenho de elevado custo. Autômatos de pilha estruturados são excelentes para se representar linguagens regulares e aspectos livre de contexto encontrados em Linguagem Natural, uma vez que é possível decompo-los em uma camada reguar (implementada com máquina de estados finitos) e uma livre de contexto (representada por uma pilha). Tais dispositivos aceitam linguagens determinísticas e livre de contexto em tempo linear. Dessa forma, trata-se de um dispositivo adequado para ser empregado como mecanismo subjacente para os autômatos adaptativos, que permitem o tratamento - sem perda de simplicidade e eficiência - de linguagens mais complexas que aquelas livres de contexo Nesta tese, dependências de contexto são tratadas com tecnologia adaptativa. Este trabalho mostra como uma regra de Linguagem Natural descrita com uma metalinguagem pode ser convertida em um autômato de pilha adaptativo. Foi possível verificar que problemas complexos em análise de Linguagem Natural, tais como os não-determinismos e ambigüidades presentes em situações de concordância, subcategorização, coordenação podem ser resolvidos com eficiência. De fato, todos os mecanismos adaptativos para solucionar estes problemas apresentam desempenho O(n). Uma arquitetura para processamento em Linguagem Natural é apresentada.

Since low-complexity language formalisms are too weak to handle NL, stronger formalisms are required, most of them resource demanding, hard to use or unpractical. Structured pushdown automata are excellent to represent regular and context-free aspects on NLs by allowing them to be split into regular layer (implemented as finite-state machines) and a context-free one (represented by a pushdown store). Such devices accepts deterministic context-free languages in linear time, and is suitable as un underlying mechanism for adaptive automata, allowing handling - without loss of simplicity and efficiency - languages more complex than context-free ones. In this thesis context dependency is handled with adaptive technology. This work shows as a Natural Language rule described with a metalanguage can be converted into adaptive structured pushdown automata. It was possible to verify that complex problems in Natural Language parsing e.g., nondeterminisms and ambiguities present in agreement, subcategorization, coordination can be solved with efficiency. In fact, all adaptive mechanisms attached to these problems have O(n) performance. An adaptive architecture for NL Language processing is presented.