Please enable JavaScript.
Coggle requires JavaScript to display documents.
AUTÓMATAS Y LENGUAJES FORMALES - Coggle Diagram
AUTÓMATAS Y LENGUAJES FORMALES
Alfabeto
:
definición
es un conjunto finito no vacío de elementos llamados símbolos
ejemplos
∑={a,b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}, es el alfabeto latino
∑={0, 1}, es el alfabeto binario
letra o símbolo
∑
aplicaciones
Desarrollo de Lenguajes de Programación
el alfabeto define el conjunto de símbolos válidos que pueden utilizarse para escribir código fuente
Expresiones Regulares y Búsqueda de Patrones
las expresiones regulares utilizan símbolos del alfabeto para definir patrones de búsqueda y manipular cadenas de texto en función de reglas predefinidas.
Gramáticas Formales y Análisis Sintáctico
definen la estructura de los lenguajes y cómo se pueden construir las cadenas válidas
Cadena o palabra
definición
Una cadena o palabra es una secuencia finita de símbolos tomados del alfabeto
ejemplos
las cadenas podrían ser "101", "0", "1101", etc
Alfabeto de Letras Mayúsculas {A, B, ..., Z}:
Cadena "HELLO"
Cadena "COMPUTER"
Cadena "ABC"
Cadena "XYZ"
letra o símbolo
W
Longitud de una cadena
se refiere a
la cantidad de caracteres que componen esa cadena.
ejemplos
longitud de la cadena "Hola" es 4.
longitud de la cadena "123456" es 6.
longitud de la cadena "Este es un ejemplo." es 18 (incluyendo el espacio y el punto final).
aplicaciones
Manipulación de Cadenas
Validación de Entrada de Datos
Optimización de Almacenamiento
Diseño de Interfaces de Usuario
Lenguaje
definición
Un lenguaje es un conjunto de cadenas construidas utilizando símbolos de un alfabeto dado. Puede ser finito o infinito.
letra o símbolo
L
Ejemplos
Lenguaje de Palíndromos en Alfabeto Binario:
Este lenguaje consiste en todas las cadenas binarias que se leen igual de izquierda a derecha y de derecha a izquierda.
"101", "11011", "111", "00"
Lenguaje de Palabras en un Alfabeto de Vocales:.
el lenguaje consta de todas las combinaciones posibles de vocales en un alfabeto. Por ejemplo, si el alfabeto de vocales es {a, e, i, o, u}, el lenguaje incluiría palabras como "a", "ai", "eiu", "oaei", etc
Lenguaje regular
ejemplo
Lenguaje de Cadenas Binarias Pares:
contiene todas las cadenas binarias con un número par de 0's y 1's.
Ejemplo: { "", "00", "1010", "110011", ... }
definición
es un tipo de lenguaje formal que puede ser descrito o reconocido por un autómata finito o expresado mediante una expresión regular
Características
Cualquier lenguaje finito es regular.
Los lenguajes regulares son cerrados bajo operaciones regulares.
La unión, concatenación y cierre de Kleene de lenguajes regulares también es un lenguaje regular.
Aplicaciones
Búsqueda de Patrones en Texto
Validación de Datos
Análisis Léxico en Compiladores
Por comprensión
ejemplo
Definir el conjunto de números naturales pares
Conjunto de números pares = {x | x es un número natural y x es divisible por 2}
Aplicaciones
Expresiones Regulares Avanzadas
Identificación de Patrones Complejos
definición
En el contexto de lenguajes formales y teoría de autómatas implica describir las propiedades, reglas o características que deben cumplir los elementos del conjunto
Por Extensión
ejemplo
Definir el conjunto de vocales en el alfabeto inglés
Conjunto de vocales = {a, e, i, o, u}
Aplicaciones
Patrones de Búsqueda Personalizados
Expresiones Regulares Personalizadas
definición
En el contexto de lenguajes formales y teoría de autómatas implica enumerar explícitamente todos los elementos individuales que pertenecen al conjunto
aplicaciones
Desarrollo de Compiladores:
son fundamentales para el diseño y desarrollo de compiladores.
Análisis de Lenguaje Natural:
los lenguajes formales se utilizan en el procesamiento del lenguaje natural para analizar y comprender el significado y la estructura de las oraciones en lenguaje humano.
expresiones regulares
Definición
es una cadena de caracteres que define un patrón de búsqueda en un texto
ejemplos
Detección de Correos Electrónicos:
Expresión Regular: [a-zA-Z0-9._%+-]+
[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}
Coincidirá con:
usuario@dominio.com
Detección de Fechas (Formato MM/DD/YYYY):
Expresión Regular: (0[1-9]|1[0-2])/(0[1-9]|[12][0-9]|3[01])/[0-9]{4}
Coincidirá con: 08/21/2023
aplicaciones
procesamiento de texto:
en editores de texto y procesadores de texto
Programación:
Para buscar, reemplazar o validar cadenas en lenguajes de programación como Python, JavaScript, Java, y más.
Bases de Datos:
Para buscar y filtrar información en bases de datos.
Estado
ejemplos
en el
autómata cambia de estado a medida que procesa cada símbolo de entrada, siguiendo las transiciones definidas por las reglas del autómata
autómata finito que reconoce el lenguaje de cadenas binarias que terminan en "0". Los posibles estados podrían ser "q0" (estado inicial), "q1" (estado donde se ha leído al menos un"0"), y "q2" (estado final)
definición
se refiere a una
configuración particular o condición en la que se encuentra un autómata en un momento dado
se utilizan para
representar las diferentes etapas de procesamiento de una cadena en un lenguaje formal
aplicaciones
Diseño de Compiladores
representan los diferentes estados de procesamiento, como palabras clave, identificadores, números, operadores, etc.
Reconocimiento de Lenguajes
Permiten al autómata reconocer si la cadena pertenece o no al lenguaje definido.
Transición
Ejemplos
Estado Actual (Origen)
estado en el que se encuentra el autómata antes de realizar la transición.
Símbolo de Entrada
Es el símbolo leído por el autómata que desencadena la transición
Estado Siguiente (Destino)
Es el estado al que el autómata se mueve después de realizar la transición.
aplicaciones
Compiladores
Analizadores Léxicos y sintácticos
Verificación Formal de Sistemas:
definición
es un cambio de estado que ocurre en un autómata en respuesta a la lectura de un símbolo de entrada
Gramática
formal
Ejemplos
Lenguaje de Palíndromos en Alfabeto {a, b}:
S -> ε | a | b | aSa | bSb Esta gramática genera palíndromos formados por los símbolos 'a' y 'b'. Por ejemplo, "aba", "abba", "aa", etc.
aplicaciones
Desarrollo de Compiladores y Analizadores Sintácticos:
Las gramáticas se utilizan para definir la sintaxis de los lenguajes de programación.
Análisis de Lenguaje Natural y Procesamiento de Texto:
Las gramáticas se aplican en el análisis de lenguaje natural para entender y extraer significado de oraciones.
definición
es un
conjunto de reglas que definen cómo se pueden construir las cadenas válidas en un lenguaje
se utilizan para
describir la estructura sintáctica de los lenguajes
Clasificación Jerárquica de las Gramáticas
definición
propuesta por Noam Chomsky una jerarquía organiza las gramáticas en cuatro niveles, desde las más restrictivas hasta las más generales
Ejemplos
Tipo 0: Gramáticas Irrestrictas
Máquinas de Turing
No hay restricciones en las reglas de producción.
Tipo 1: Gramáticas Contextuales
autómatas linealmente acotadas
Las reglas de producción son de la forma α → β, donde α es una cadena de símbolos y β es una cadena que puede reemplazar a α solo en contextos específicos.
Tipo 2: Gramáticas Libres de Contexto
autómatas de pila
Las reglas de producción son de la forma A → γ, donde A es un símbolo no terminal y γ es una cadena de símbolos (terminales y no terminales).
Tipo 3: Gramáticas Regulares
autómatas finitos
Las reglas de producción son de la forma A → aB o A → a, donde A y B son símbolos no terminales y a es un símbolo terminal.
aplicaciones
clasificación de los diferentes tipos de lenguajes según su complejidad.
Operaciones regulares
son
ejemplos
Unión y Estrella (A ∪ B)*:
Expresión Regular: (a|aa|aaa|b|bb|bbb)
Lenguaje Resultante: Cualquier combinación de cadenas de "a"s y "b"s, incluyendo la cadena vacía.*
aplicaciones
permiten construir nuevos lenguajes a partir de lenguajes regulares existentes
definción
Las operaciones regulares se aplican a lenguajes regulares en el contexto de la teoría de autómatas y lenguajes formales
operaciones regulares más comunes
Estrella de Kleene (A)*
La estrella de Kleene de un lenguaje A consiste en todas las cadenas que se pueden formar tomando cero o más repeticiones de cadenas de A.
ejemplo expresión Regular: (a|aa|aaa)*
Lenguaje Resultante: {ε, a, aa, aaa, aaaa, aaaaa, ...} (cualquier cantidad de "a"s, incluyendo ninguna)
concatenación (AB)
concatenación de dos lenguajes A y B consiste en todas las cadenas que se pueden formar al tomar una cadena de A seguida de una cadena de B.
ejemplo expresión Regular: (a|aa|aaa)(b|bb|bbb)
Lenguaje Resultante: {a, aa, aaa, b, bb, bbb}
Unión (A ∪ B)
La unión de dos lenguajes A y B consiste en el conjunto de cadenas o palabras que pertenecen a los lenguajes A o B
tenemos dos lenguajes regulares A y B
Lenguaje A: {a, aa, aaa} y Lenguaje B: {b, bb, bbb}
ejemplo expresión Regular: (a|aa|aaa) ∪ (b|bb|bbb)
Lenguaje Resultante: {a, aa, aaa, b, bb, bbb}
Operador
definición
es una función o símbolo que realiza una operación específica sobre uno o más elementos y produce un resultado
ejemplos
Operador de Unión (∪)
Operador de Intersección (∩)
Operador de Diferencia (-)
Precedencia de los operadores.
definición
se refiere al orden en el que se evalúan las operaciones en una expresión que involucra múltiples operadores.
Es una convención que establece qué operaciones se realizan primero y cuáles se realizan después
ejemplos
Operadores Aritméticos:
Multiplicación (*) y división (/)
se evalúan antes que la suma (+) y resta (-).
aplicaciones
programción
Matemáticas Computacionales
aplicaciones
manipulación y análisis de conjuntos
la teoría de autómatas
matemáticas
informática
Autómata Finito
definición
es un modelo matemático abstracto que representa un sistema que puede estar en diferentes estados y que cambia de un estado a otro en respuesta a la entrada que recibe.
ejemplos
q1" (estado donde se ha leído al menos un "0")
"q2" (estado final)
reconoce el lenguaje de cadenas binarias que terminan en "0". Los posibles estados podrían ser "q0" (estado inicial)
Autómata Finito No Determinista AFND
ejemplos
para Reconocer Cadenas con "abc"
Este autómata acepta cadenas que contienen la subcadena "abc".
Conjunto de estados: {q0, q1, q2, q3}
Alfabeto: {a, b, c}
Estado inicial: q0
Estado de aceptación: q3
Función de transición:
δ(q0, a) = {q0}
δ(q0, b) = {q0}
δ(q0, c) = {q0, q1}
δ(q1, a) = {q2}
δ(q2, b) = {q3}
δ(q3, c) = {q3}
aplicaciones en
lenguajes formales para representar sistemas que siguen una secuencia de estados bien definida en respuesta a la entrada
la teoría de autómatas
definición
es un modelo matemático abstracto que consiste en un conjunto finito de estados, un alfabeto de entrada finito, una función de transición que define cómo el autómata cambia de estado en función del símbolo de entrada, un estado inicial y un conjunto de estados de aceptación
aplicaciones
teoría de lenguajes formales
construcción de compiladores
análisis de lenguaje natural
diseño de protocolos de comunicación
Autómata Finito Determinista AFD
ejemplos
para Reconocer Cadenas de 0's y 1's:
Este autómata acepta cadenas de 0's y 1's donde la última cifra debe ser 1.
Conjunto de estados: {q0, q1}
Alfabeto: {0, 1}
Estado inicial: q0
Estado de aceptación: q1
Función de transición:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q1
δ(q1, 1) = q1
definición
es un modelo matemático abstracto que consiste en un conjunto finito de estados, un alfabeto de entrada finito, una función de transición que define cómo el autómata cambia de estado en función del símbolo de entrada, un estado inicial y un conjunto de estados de aceptación
aplicaciones
modelar sistemas con comportamientos discretos y secuenciales
la teoría de autómatas