Please enable JavaScript.
Coggle requires JavaScript to display documents.
AUTOMATAS Y LENGUAJES FORMALES, Autor: Wilmer Alejandro Barragán Durán -…
AUTOMATAS Y LENGUAJES FORMALES
ALFABETO
según
Martínez y García (2005, p. 1)
es
Conjunto finito y no vacío de elementos llamados símbolos.
determinados por
Extensión, enumeración de símbolos o por comprensión.
para
Especificar determinada propiedad que la totalidad de los símbolos debe realizar.
1 more item...
PALABRA O CADENA
según
Jurado, E. (2008, p. 16)
es
"Secuencia finita de símbolos de un alfabeto"
ejemplos
x = casa es una palabra definida sobre el alfabeto ∑1 y= 010100 es una palabra definida por el alfabeto ∑2
tipos
Palabra vacía
: No posee ningún símbolo, se representa con (⋋)
Longitud de palabra
: Número de símbolos que constituyen la palabra, se representa con (||).
Lenguaje
según
Malaga (2008, p. 16)
es
Dentro del contexto del alfabeto alude el grupo de todas las palabras que se pueden conseguir con las letras de dicho alfabeto
se
Representa con ω(∑). Además, este lenguaje es infinito, y, siempre pertenece a él la palabra vacía.
ejemplo
Si ∑ = {a} entonces ω(∑) = { ⋋, a,aa,aaa,...}
EXPRESIÓN REGULAR
las
Expresiones (e.r) regulares facilitan la representación de los lenguajes regulares.
por otro lado
Es expresiones regulares sobre un ∑ y el lenguaje que indican se determina como.
ejemplo
Si α,β son e.r que definen los lenguajes A y B
entonces
αβ es una e.r que denota A.B
α + β es una e.r que denota A ∪ B
ESTADO
es
Condición donde se encuentra un sistema en determinado momento Son importantes en la modelización y análisis de sistemas dinámicos, como, por ejemplo, en los autómatas finitos.
en
Un autómata finito, el estado manifiesta una configuración específica en la que se halla el autómata en algún momento preciso durante su ejecución.
también
Los estados se pueden emplear para representar distintas condiciones o situaciones en un sistema.
ejemplo
En un sistema de semáforos, tenemos tres estados: rojo, amarillo y verde, donde cada estado manifiesta el color actual del semáforo y las transiciones representan el cambio de color del semáforo en contestación a diversos eventos.
LENGUAJE REGULAR
es
El lenguaje generado por medio de una gramática regular, y está formado por la concatenación de símbolos, y no se encuentra relación entre una parte de la cadena y otra parte de la cadena.
ejemplos
Φ, {ɛ}, para todo a ∈ ∑ {a} es un lenguaje regular, si A y B son lenguajes regulares, entonces: A u B, A . B son lenguales regulares.
Lenguaje regular por extensión:
es
Cada una de las cadenas que pertenecen al lenguaje
ejemplo
1 more item...
Lenguaje regular por comprensión:
se
Define mediante una regla o patrón que causaría todas las cadenas válidas.
Si tenemos el lenguaje L que contiene todas las cadenas de Os y 1s con un número par de Os se puede delimitar por comprensión como L ={ ω | w contiene un número par de 0s}.
AUTOMATAS FINITOS
es
Un modelo matemático de una máquina que permite cadenas de un lenguaje definido sobre un alfabeto A. Unicer.edu.ar (2009).
clases
2
Autómata finito NO determinista (AFND):
estos
A diferencia de los AFD, en los AFND se pueden encontrar varias opciones de transición, además, con ⋋ - transiciones que se ejecutan sin tener en cuenta los símbolo de la cadena de entrada..
también
1 more item...
1
Autómata finito determinista (AFD):
es
Máquinas teóricas que van transformando su estado a partir de la entrada que reciban, y, su salida se limita a dos valores (aceptado y no aceptado)
también
1 more item...
TRANSICIONES
se
Refiere al cambio de estado que ocurre en un autómata en respuesta a la entrada de un símbolo
las
Transiciones son muy importantes para el funcionamiento de los autómatas porque determinan cómo el autómata se mueve mediante distintos estados en respuesta a las entradas recibidas.
en
Un AFD cada estado y cada símbolo de entrada, hay idénticamente una transición definida hacia otro estado.
en
Un AFND se pueden encontrar diferentes transiciones probables para un mismo estado y símbolo de entrada.
GRAMÁTICA FORMAL
según
Amaya (2011, p. 66).
es
Conjunto de reglas para conformar efectivamente las frases de un lenguaje
las
Reglas gramaticales: Son la expresión de la forma ω → β en donde así como ω como β son cadenas de símbolos en donde pueden aparecer tanto elementos del alfabeto ∑ como nuevos símbolos denominados variables.
ejemplo
La gramática del español, ingles, aleman, etc.
OPERACIONES REGULARES
son
Las distintas operaciones que se pueden realizar sobre los lenguajes formales, además pueden ser representados por autómatas finitos o expresiones regulares.
como lo son
UNIÓN:
La unión de dos lenguajes regulares L1 y L2, denota como L1 ∪ L2, esto crea un nuevo lenguaje que posee todas las cadenas que pertenecen a L1 o a L2, o a ambas.
la
CONCATENACIÓN:
La concatenación de dos lenguajes regulares L1 y L2, señala como L1 . L2, esto crea un nuevo lenguaje que posee todas las cadenas que se pueden formar concatenando una cadena de L1 con otra cadena L2.
la
ESTRELLA DE KLEENE:
De un lenguaje regular L, denotada como L*, crea un nuevo lenguaje que posee todas las probables concatenaciones finitas de cadenas en L, incluida la cadena vacía (ϵ).
1 more item...
OPERADORES:
Son usados en expresiones regulares para definir patrones o conjuntos de cadenas.
Precedencia de los Operadores:
Estipulan el orden en el que se evalúan las operaciones.
tales como
ESTRELLA DE KLEENE:
Posee la mayor precedencia, denota cero o más repeticiones de la expresión regular precedente.
CONCATENACIÓN:
Esta concatenación se realiza antes que cualquier otra operación.
OPERADOR DE UNION ("|"):
Posee menor precedencia que la concatenación y se usa para indicar alternancia entre dos opciones.
SUBTEMA # 2
OPERADORES DE KLEENE:
son
Usados para especificar repeticiones de símbolos o subexpresiones regulares
tales como
1). Estrella de Kleene ("*")
2). Más de Kleene ("+")
1 more item...
Autor: Wilmer Alejandro Barragán Durán