CONTRIBUIÇÃO AO ESTUDO DE ESPAÇOS CELULARES UNIVERSAIS APLICAÇÃO EM RECONHECEDORES DE LINGUAGENS DE CONTEXTOS LIVRES

O presente trabalho se constitui em um estudo de Espaços Celulares de Computação-Construção Universais. Para provarmos a universalidade de um espaço celular particular nós desenvolvemos o projeto de um computador-Construtor Universal (CCU) realizável neste espaço. Queremos significar por CCU uma máquina capaz de computar qualquer função computável em uma máquina de Turing universal, bem como capaz de construir qualquer outra máquina construível no referido espaço, inclusive a si própria - caso que chamaremos de auto-reprodução. Uma aplicação para este espaço celular é estudada, quando simulamos um aceitador para linguagens de contexto-livre, ou seja, um push-down automator determinístico (DPDA), no CCU apresentado. Além disso são dadas as especificações de um DPDA celular particular, quando também são apresentadas as regras gerais de projeto para um DPDA genéricoThis work presents a study of Universal Computation- Construction Cellular Spaces. To proove the universality of a especific cellular space we develop a design of a Universal Computer-Contructor (UCC) realizable in that space. By UCC we mean a machine able to compute any Turing computable function, as well as able to construct any other machine constructable in the proposed space, wich case we called self-reproduction. An aplication to this cellular space has also been studied, when a particular context-free language acceptor, that is, a deterministic push-down automaton (DPDA), is simulated in the designed UCC. Besides that, the especifications of a particular cellular DPDA are defined, when general rules of construction of any generic DPDA are given