Autòmat linealment acotat: diferència entre les revisions
Contingut suprimit Contingut afegit
m Corregit: a els -> als autòmats |
m Corregit: -consisteix en que +consisteix que |
||
Línia 17:
Un autòmat linealment acotat és una màquina de Turing la cinta està formada només per cel de kn de llarg, on la longitud n és la seqüència de l'entrada ik és una constant associada al '' autòmat linealment-acotat '' particular, és a dir la quantitat de cinta que l'autòmat permet utilitzar es limita per un factor lineal k perquè quan entre una paraula de grandària n (els símbols de n), la màquina determini si la paraula és acceptable, o si la paraula està en el llenguatge de l'autòmat.
La diferència amb una màquina de Turing, consisteix
Un autòmat linealment acotat té més poder que els [[Autòmat de pila|autòmats de pila]] no determinístics, però menys poder que les màquines de Turing.
|