Diferencia entre revisiones de «Autómata finito»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 186.84.2.184 a la última edición de Muro Bot |
|||
Línea 270:
== Generalizaciones de autómatas finitos ==
[[Archivo:Mealymachine jaredwf.png|thumb|200px|Ejemplo de [[Máquina de Mealy]], un tipo de [[transductor de estados finitos]], que generaliza los autómatas finitos.]]
Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los [[transductor de estados finitos|transductores de estados finitos]] como autómatas finitos que están dotados además de un [[alfabeto]] de salida, distinto al de entrada, y que pueden poseer más de un estado inicial.<ref>{{obra citada |título=A general computational model for word-form recognition and production |apellidos=Koskenniemi |nombre=Kimmo |año=1984 |editorial=Association for Computational Linguistics |ubicación=Morristown, NJ, Estados Unidos |isbn= |página= |páginas=178-181 |url=http://acl.ldc.upenn.edu/P/P84/P84-1038.pdf |fechaacceso=10 de abril de 2010}}</ref> Las [[máquina de Moore|máquinas de Moore]] y [[máquina de Mealy|máquinas de Mealy]] son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar [[sistema secuencial|sistemas secuenciales]].<ref>{{cita publicación |apellido=Moore |nombre=Edward F. |título=Gedanken-experiments on Sequential Machines |url=http://books.google.cl/books?hl=es&lr=&id=oL57iECEeEwC&oi=fnd&pg=PA129&dq=Gedanken-experiments+on+Sequential+Machines&ots=xtIZlfNSh3&sig=_IZbeMzi9_E7N5vQpocPAfK1KiU#v=onepage&q=Gedanken-experiments%20on%20Sequential%20Machines&f=false |idioma=inglés |publicación=Automata Studies, Annals of Mathematical Studies |editorial=Princeton University Press |fecha=1956 |ubicación=Princeton, N.J. |número=34 |páginas=129–153 |fechaacceso=10 de abril de 2010}}</ref><ref>{{cita publicación |apellido=Mealy |nombre=George H. |título=A Method for Synthesizing Sequential Circuits |idioma=inglés |publicación=Bell Systems Technical Journal |fecha=1955 |volumen=34 |páginas=1045-1079 |fechaacceso=10 de abril de 2010}}</ref>
Es incluso posible aumentar el poder de [[computabilidad|cómputo]] de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo [[Pila (informática)|pila]] para ser considerada en cada transición. Esta es la idea utilizada por los llamados [[autómata con pila|autómatas con pila]], los cuales son capaces de reconocer [[gramática libre de contexto|lenguajes libres de contexto]], que están un nivel por sobre los [[lenguaje regular|lenguajes regulares]] en la [[Jerarquía de Chomsky]].<ref>{{obra citada |título=Formal languages and their relation to automata |apellidos=Hopcroft |nombre=John E. |enlaceautor=John E. Hopcroft |apellidos2=Ullman |nombre2=Jeffrey D. |enlaceautor2=Jeffrey D. Ullman |año=1969 |editorial=Addison-Wesley Longman Publishing Co., Inc. |ubicación=Boston, MA, Estados Unidos |páginas=262 |url=http://portal.acm.org/citation.cfm?id=1096945 |fechaacceso=10 de abril de 2010}}</ref>
Línea 288 ⟶ 279:
* [[Lenguaje regular]]
* [[Teoría de autómatas]]
== Referencias ==
| |||