Un idioma es un conjunto de cadenas sobre un alfabeto. Esto significa que para cualquier cadena, Z, en el idioma, debe estar compuesta por una secuencia de caracteres de algún alfabeto. Guay.
Una máquina de estados finitos es aquella que tiene un conjunto finito de estados en los que puede estar. Sin pérdida de generalidad, esto puede considerarse como el conjunto de números {1, …, N}. Algunos de estos estados, un subconjunto F de {1, …, N} se consideran estados “aceptados”. La máquina se inicia en un estado inicial, digamos el estado 1, y lee en una cadena un carácter a la vez. Según el carácter que se lea y el estado en el que se encuentra actualmente la máquina, la máquina cambia de estado. Esto se puede encapsular en una función de transición que mapea pares con un estado desde {1, …, N} y un carácter del alfabeto a otro estado en {1, …, N}. La máquina acepta la cadena que está leyendo si, después de leer el último carácter, la máquina está en uno de los estados de aceptación.
¿Qué tiene esto que ver con los idiomas normales? Definición: Un lenguaje se llama regular si puede ser reconocido por alguna máquina de estados finitos. Esto significa que existe una máquina que acepta todas las cadenas en el idioma y sin cadenas que no están en el idioma.
- ¿Qué es la secuencia de arranque, publicación y bios? ¿Qué viene primero?
- ¿Cómo está cambiando el aprendizaje automático la publicidad en línea?
- ¿Cuáles son algunos desarrollos sorprendentes en el campo del procesamiento del lenguaje natural?
- ¿Cuál era el tamaño de la memoria de la computadora básica?
- ¿Cómo se utilizará el aprendizaje automático en el software empresarial, particularmente en las prácticas ITSM?
Entonces, la importancia y la aplicación de los lenguajes regulares es que cada uno de ellos puede identificarse mediante algún programa simple, que puede tomar la siguiente forma:
fn aceptar (str) {
estado = 1
para char en str:
estado = transición (estado, char)
si el estado en F:
volver verdadero
más:
falso retorno
}
Esto es extremadamente útil en compiladores y muchos otros programas (grep en Unix es un gran ejemplo), ya que ha decidido su respuesta cuando haya terminado de leer su entrada. Hay un escalofrío no trivial de problemas que puede reducirse al reconocimiento de un lenguaje regular.
