Please enable JavaScript.
Coggle requires JavaScript to display documents.
autómatas y lenguajes formales - Coggle Diagram
autómatas y lenguajes formales
alfabeto
Un alfabeto es un conjunto de símbolos finito y no vacío, definido ya sea por la lista de sus símbolos o por una característica que todos los símbolos cumplen.
Lenguaje
Un lenguaje es un conjunto de cadenas de símbolos que obedecen reglas sintácticas. Puede ser simple o complejo, abarcando desde lenguajes naturales hasta lenguajes formales en programación y teoría de la computación.
Ejemplo
Si Σ = {0,1} podríamos definir los lenguajes
“conjunto de cadenas en Σ que terminan en 0”
algunos de las palabras del lenguajes serían: 0,
10,00,010,100, 110…
Autómata Finito Determinista
Es un autómata finito en el cual δ (delta) representa una función de transición, significando que para cada combinación (estado actual y símbolo de entrada), hay asignado un único estado siguiente.
Autómata Finito No Determinista
es un autómata finito donde δ no es una función única de transición. Esto implica que para un estado y símbolo de entrada, pueden existir cero, uno, dos o más estados siguientes. En un Autómata Finito No Determinista, esta relación se suele representar con el símbolo ∆ en vez de δ.
Cadena
Es la unión de símbolos pertenecientes a un alfabeto Σ, dispuestos en secuencia contigua, es decir, uno después del otro.
Ejemplos
Para el alfabeto Σ = {a,b,c,…z} algunas cadenas son:
ab, z, cc, abc, abab
Para el alfabeto Σ = {0,1} algunas cadenas son:
0, 1, 01, 000, 0101
Expresión regular
una expresión regular es una notación normalizada para describir lenguajes regulares generados por gramáticas de tipo 3. Estas expresiones permiten representar con precisión y simplicidad cualquier lenguaje regular utilizando símbolos del alfabeto Σ, junto con λ y Ø.
Ejemplos
01 + 001 es una e.r. que representa al lenguaje L = {01, 001}
0∗10∗ es una e.r. que representa a cualquier cadena binaria en la que hay un
solo 1, L = {0n10m/n, m ≥ 0}
Sea Σ = {a, b, c}
a(a + b + c)∗ representa a cualquier cadena que empiece por a
(a + b + c)∗ representa al lenguaje universal definido sobre el alfabeto
Lenguaje regular
los lenguajes regulares sobre un alfabeto dado ∑ son todos los lenguajes que se pueden formar a partir de los lenguajes básicos Ø, {λ}, {α}, α ∈ Σ,por medio de las operaciones de unión, concatenación y estrella de kleene.
Ø, {λ} y {α}, para cada α ∈ Σ, son lenguajes regulares sobre Σ. Estos son los denominados lenguajes regulares básicos.
Si A y B son lenguajes regulares sobre Σ, también lo son:
si A ∪ B (unión),
A . B (concatenación),
A* (estrella de Kleene).
Por Extensión
Se define enumerando explícitamente todas las cadenas que pertenecen al lenguaje. Por ejemplo, el conjunto de todas las palabras de tres letras en el alfabeto {a, b} sería un lenguaje regular por extensión: {aaa, aab, aba, abb, baa, bab, bba, bbb}.
por comprensión
Se define mediante una propiedad o regla que deben cumplir todas las cadenas en el conjunto. Por ejemplo, el conjunto de todas las cadenas que comienzan con 'a' y terminan con 'b' en el alfabeto {a, b} sería un lenguaje regular por comprensión: {ab, aab, aaab, ...}.
Estado
Es una configuración en la que puede encontrarse un autómata en un momento dado. Los estados se utilizan para representar la información almacenada en el autómata
transición
Es una función que describe cómo el autómata cambia de un estado a otro cuando se procesa una entrada. Las transiciones se representan mediante una tabla o un diagrama de transición
La gramática formal
Es una construcción de naturaleza lógico-matemática empleada para establecer las secuencias de caracteres permitidas en un lenguaje formal específico o en una lengua natural.
Estado Inicial
El estado desde el cual comienza la computación del autómata.
Ejemplo: En un AFD que reconoce números binarios pares, el estado inicial podría ser "paridad par".
Aplicaciones: En sistemas de control de hardware, donde ciertas acciones deben ejecutarse desde un estado inicial.
Estado de Aceptación
Ejemplo: En un AFD que valida direcciones de correo electrónico, un estado de aceptación podría indicar que la dirección es válida.
Aplicaciones: Validación de datos en formularios web, verificación de entradas en sistemas de seguridad.
Un estado en el que el autómata completa su procesamiento y acepta la cadena de entrada.
Expresión Regular
Repetición Opcional
La expresión regular "colou?r" acepta "color" y "colour".
Aplicaciones: Búsqueda de términos con variaciones de ortografía en un motor de búsqueda.
Indica que el símbolo o grupo anterior puede aparecer cero o una vez en la cadena.
Agrupación y Alternancia
Ejemplo: La expresión regular "(apple|orange)" acepta "apple" o "orange".
Aplicaciones: Filtrado de contenido en redes sociales, búsqueda avanzada en editores de texto.
Agrupa símbolos o subexpresiones para aplicar operadores sobre ellos, como la alternancia (|) para elegir entre opciones.