Autòmat linealment acotat: diferència entre les revisions

 

== Història ==

Si bé les màquines abstractes introduïdes fins llavors tenien com a objectiu el càlcul de funcions, amb el temps els investigadors es van encarregar d'estudiar la potència de les màquines com reconeixedores de llenguatges.

 

 

== Autòmats lineals ==

Els autòmats linealment acotats són similars a una [[màquina de Turing]], sabem que aquesta última té una cinta infinita.

 

 

== Components ==

Un autòmat linealment acotat està format pels següents components:

 

 

== Llenguatges no reconeguts per un autòmat linealment acotat ==

* Llenguatges recursivament enumerables