ALFABETO

PALABRA O CADENA

Martínez y García (2005, p. 1)

Conjunto finito y no vacío de elementos llamados símbolos.

Extensión, enumeración de símbolos o por comprensión.

Especificar determinada propiedad que la totalidad de los símbolos debe realizar.

EXPRESIÓN REGULAR

ESTADO

LENGUAJE REGULAR

AUTOMATAS FINITOS

"Secuencia finita de símbolos de un alfabeto"

x = casa es una palabra definida sobre el alfabeto ∑1 y= 010100 es una palabra definida por el alfabeto ∑2

Dentro del contexto del alfabeto alude el grupo de todas las palabras que se pueden conseguir con las letras de dicho alfabeto

Representa con ω(∑). Además, este lenguaje es infinito, y, siempre pertenece a él la palabra vacía.

Un modelo matemático de una máquina que permite cadenas de un lenguaje definido sobre un alfabeto A. Unicer.edu.ar (2009).

Autómata finito NO determinista (AFND):

Autómata finito determinista (AFD):

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)

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..

Los AFD son como listas ordenadas de elementos (AFD = (∑,Q,f, q0,F))

∑ = alfabeto de entrada, Q = conjunto finito y no vacío de los estados de Autómata, f = función de transición que indica en qué situaciones el Autómata pasa de un estado a otro (se define f : Q X ∑ → Q), q0 = ∈ Q es el estado inicial, F ∁ Q = conjunto de estados finales de aceptación (F ≠ ⦰).

Se definen como una lista ordenada de elementos

AFND = (∑,Q,f, q0,F,T), f : Q x ∑ → 2^Q
∑ = alfabeto de entrada, Q = conjunto finito y no vacío de los estados de Autómata, f = función de transición que indica en qué situaciones el Autómata pasa de un estado a otro (se define f : Q X ∑ → Q), q0 = ∈ Q es el estado inicial, F ∁ Q = conjunto de estados finales de aceptación (F ≠ ⦰), 2^Q = conjunto formado por los subconjuntos de Q, incluyendo a ⦰, T = relación binaria definida sobre Q que indica las ⋋ - transiciones del autómata.

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.

Φ, {ɛ}, para todo a ∈ ∑ {a} es un lenguaje regular, si A y B son lenguajes regulares, entonces: A u B, A . B son lenguales regulares.

Expresiones (e.r) regulares facilitan la representación de los lenguajes regulares.

Es expresiones regulares sobre un ∑ y el lenguaje que indican se determina como.

Si α,β son e.r que definen los lenguajes A y B

Lenguaje regular por extensión:

Lenguaje regular por comprensión:

Cada una de las cadenas que pertenecen al lenguaje

Define mediante una regla o patrón que causaría todas las cadenas válidas.

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.

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.

Los estados se pueden emplear para representar distintas condiciones o situaciones en un sistema.

TRANSICIONES

Refiere al cambio de estado que ocurre en un autómata en respuesta a la entrada de un símbolo

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.

Un AFD cada estado y cada símbolo de entrada, hay idénticamente una transición definida hacia otro estado.

GRAMÁTICA FORMAL

Conjunto de reglas para conformar efectivamente las frases de un lenguaje

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.

OPERACIONES REGULARES

Las distintas operaciones que se pueden realizar sobre los lenguajes formales, además pueden ser representados por autómatas finitos o expresiones regulares.

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.

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.

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 (ϵ).

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.

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.

SUBTEMA # 1:
CERRADURA POSITIVA.

Utiliza para denotar una o más repeticiones de la expresión regular precedente. Se aplica agregando el símbolo "+" después de la expresión regular.

Hallarla, se realizan todas las concatenaciones probables de 1,2,3. o más palabras del lenguaje:

1). {a,bc} ={a,bc,aa,abc,bca,bcbc, aaa, aabc, abca, abcbc, bcaa, bcbca, bcbcbc,...
2). {ϵ}^+ ={ϵ}
3). ∅^+ = {}

SUBTEMA # 2
OPERADORES DE KLEENE:

Usados para especificar repeticiones de símbolos o subexpresiones regulares

1). Estrella de Kleene ("*")
2). Más de Kleene ("+")

Estimemos un autómata finito que valida números binarios. Usando la estrella de Kleene, se podría señalar que después de cada "0" o "1". Podríamos reconocer cualquier cantidad de dígitos binarios ininterrumpidos en la entrada.
Su expresión sería: (0/1)^*