Sistemas Numericos
Enviado por romango • 21 de Octubre de 2013 • 239 Palabras (1 Páginas) • 245 Visitas
Con Movimiento E (Nfa- E).
Un autómata finito no determinístico con movimiento e (entrada vacía) es como la quinta tupla (Q, S, d , q0, F) con todos sus componentes igual que a un NFA, con excepción de d , la función de transición, que ahora transforma Q x (S È {e }) a 2Q; para incluir transiciones de un estado a otro que no dependan de ninguna entrada
Se puede añadir una columna en la tabla de d para colocar los pares de la forma (qi, e). Cuando hay e -transiciones en un NFA es conveniente suponer que cada estado tiene una e -transición que cicla en ese estado.
Ejemplo: el lenguaje consistente en cualquier número (incluyendo el cero) de 0’s seguidos por cualquier número de 1’s seguido, a su vez, por cualquier número de 2’s
Lenguajes Regulares
Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos - programas que analizan un texto y extraen los lexemas (o unidades léxicas) que hay en el mismo.
El conjunto de los lenguajes regulares sobre un alfabeto S esta formado por el lenguaje vacío, los lenguajes unitarios incluido {e} y todos los lenguajes obtenidos a partir de la concatenación, unión y cerradura de estrella de lenguajes.
Ejemplo de lenguajes regulares:
Expresión Regular | Lenguaje Regular |
10 | L={La cadena de 10} |
1 + 0 | L={Una cadena de 0 ó una cadena de 1} |
1* | L={Cualquier cadena de 1’s incluyendo e } |
(00)* | L={Cadenas de 0’s de longitud par, incluyendo e } |
...