Son modelos de comportamiento de un sistema o un objeto complejo, con un número limitado de modos o condiciones predefinidos, donde existen transiciones de modo:AUTOMATA: Es algo que trata de evitar funciones propias del ser humano. veamos:
• modelo matemático que realiza cómputos de forma automática sobre una entrada para producir una salida.
• Modelo que posee sintaxis y semántica formales y que sirve para representar aspectos dinámicos que no se expresan en otros diagramas.
• una herramienta muy útil para especificar aspectos relacionados con tiempo real, puede ser electrónico o computacional o de otro tipo como circuitos, arquitecturas de software, etc.
PORQUE ESTA CONFORMADA?
Está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto, y leyendo a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
CUAL ES SU FINALIDAD?
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
AUTÓMATA FINITO DETERMINISTA:
• (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).
• En un AFD no pueden darse ninguno de estos dos casos:
• Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.
• Un ejemplo interesante de autómat as finitos deterministas son los tries.
AUTOMATAS FINITOS NO DETERMINISTAS
Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
• Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
• Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.
- extraido de exposicion de compañeros
A=(E,S,Q,F,G)
E = conjunto de entradas alfabeto
S = Salidad
Q = Los estados
F = función transición que cumpla reglas
G = Función de salidas
nota: tomado de las explicaciones del Ingeniero
Veamos un ejemplo.
EXPRESIONES REGULARES
Las expresiones regulares son llamadas también patron, que son un conjunto de cadenas sin enumerar sus elementos, de tal forma que podemos comparar el patrón con otro conjunto de caracteres para ver las coincidencias. Por ejemplo:
- Un conjunto de cadenas, handel, handel, y haendel, sedescribe mediante el patron “h(a/a/ae)ndel”.
- una expresion regular podemos obtener conjuntos finitos o infinitos de cadenas que corresponden a ella, es decir conjuntos regulares.
- Las expresiones Regulares permiten realizar búsquedas o expresiones de gran complejidad.
Veamos las expresiones regulares mediante este grafico:
- Para crear una expresión regular, puede utilizarse uno de los siguientes métodos exp_reg=/ab+c/ exp_reg = new RegExp("ab+c")
- La primera opción compila la expresión regular cuando se evalúa el script, por lo que es mejor cuando la expresión regular es una constante y no va a variar a lo largo de la ejecución del programa. La segunda opción compila la expresión regular en tiempo de ejecución.
Reglas que definen las expresiones regulares sobre Σ (sigma)
— R1: ∅ es una expresión regular que corresponde al lenguaje vacío.
— R2: λ es una expresión regular que corresponde al lenguaje {λ}, o sea, al lenguaje que contiene la cadena vacía.
— R3: Si a es un símbolo de Σ, entonces a es una expresión regular que corresponde al lenguaje {a}, o sea, al lenguaje que contiene la cadena a.
— R4: Si r y s son dos expresiones regulares sobre Σ que
— corresponden a los lenguajes L(r) y L(s) respectivamente,
entonces:
— R4.1: (r) | (s) es una expresión regular que corresponde a L(r) ∪ L(s).
— R4.2: (r)(s) es una expresión regular que corresponde a L(r)L(s).
— R4.3: (r)* es una expresión regular que corresponde a L(r)*.
— R4.4: r es una expresión regular que corresponde a L(r).
— R5: Sólo expresiones que se pueden producir usando las
— reglas R1- R4 son expresiones regulares sobre Σ.
PROPIEDADES ALGEBRAICAS DE LAS EXPRESIONES REGULARES
— - | es conmutativo: r | s = s | r
— - | es asociativo: r | (s | t) = (r | s) | t
— - La concatenación es asociativa: (rs)t = r(st)
— - La concatenación distribuye sobre |: r(s | t) = rs | rt
— (s | t)r = sr | tr
— - λ para la concatenación: λr = r, r λ = r
— - r* = (r+ | λ)
— - * es idempotente: r** = r*
Ø Definición regular para el conjunto de identificadores que se definen como cadenas de letras y dígitos que comienzan con una letra.
— <letra> → A | B | C | … | Z | a | b | c | … | z
— <dígito> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
— <identificador> → <letra>(<letra>|<digito>)*
Expresiones irregulares 2.pdf-adobe Reader
—Compiladores(1).pdf-adobe Reader
