1. Alfabeto
1.1. Definición:
1.1.1. Conjunto finito y no vacío cuyos elementos se denominan símbolos. Para designarlo se utilizan letras mayúsculas del alfabeto griego, especialmente Σ y Γ.
1.2. Ejemplos:
1.2.1. A,B,C,D,E,F..............X,Y,Z
1.2.2. O,1
1.3. Aplicaciones:
1.3.1. Definición de Cadenas: Las cadenas son secuencias de símbolos tomados del alfabeto. Un lenguaje se compone de un conjunto de cadenas construidas a partir de los símbolos del alfabeto. La definición de cadenas y lenguajes se basa en la elección de un alfabeto específico.
1.3.2. Las operaciones como la concatenación, unión y la estrella de Kleene se aplican a las cadenas que están formadas por símbolos del alfabeto. Estas operaciones permiten la manipulación y combinación de cadenas para formar nuevas cadenas o expresiones regulares.
2. Palabra o Cadena
3. Definición:
4. Definición: Una palabra o cadena es una secuencia finita de símbolos tomados de un alfabeto específico. Por ejemplo, en el alfabeto {0, 1}, "10101" es una cadena.
5. Ejemplos:
6. Lenguaje
6.1. Definición:
6.1.1. Un lenguaje es un conjunto de palabras o cadenas formadas por símbolos de un alfabeto determinado. Puede ser un conjunto infinito o finito de cadenas.
6.2. Ejemplos:
6.2.1. Lenguaje de Números Binarios Pares: Este lenguaje contiene todas las cadenas binarias que representan números pares. En el alfabeto {0, 1}, incluiría "00", "110", "1010", etc. Lenguaje de Identificadores en Programación: Este lenguaje incluye cadenas que pueden ser utilizadas como nombres de variables en la programación. Por ejemplo, "contador", "suma", "nombreDeUsuario" son ejemplos válidos.
6.3. Aplicaciones:
6.3.1. Diseño de Lenguajes de Programación: La teoría de lenguajes formales es esencial para diseñar lenguajes de programación, ya que permite definir la sintaxis y las reglas semánticas de los lenguajes.
6.3.2. Verificación y Validación de Software: Se utilizan autómatas y gramáticas para verificar y validar programas y sistemas, garantizando que cumplen con ciertas propiedades o restricciones.
6.3.3. Procesamiento de Lenguaje Natural (NLP): Los autómatas y gramáticas se emplean en la construcción de analizadores sintácticos y semánticos en NLP para entender y generar lenguaje humano de manera automatizada.
7. abcd es una cadena del alfabeto {a,b,c,d,e,0,1,2,3,4,5,6,+,*,#}
8. Aplicaciones:
9. Programación de Computadoras: En la programación, las cadenas se utilizan para representar texto y datos estructurados. Los lenguajes de programación manipulan cadenas para realizar operaciones de entrada/salida, formatear texto, procesar archivos, entre otras tareas.
10. Bases de Datos y Sistemas de Información: Las cadenas se utilizan para representar datos como nombres, direcciones y descripciones en bases de datos y sistemas de información. Las consultas y búsquedas en bases de datos a menudo involucran cadenas.
11. Procesamiento de Lenguaje Natural (NLP): En NLP, se analizan y manipulan cadenas para comprender y generar lenguaje humano. La segmentación de texto, el análisis de sentimiento, la traducción automática y la generación de texto son ejemplos de aplicaciones que involucran cadenas de palabras.
12. Automata Finito Determinista
12.1. Definicion:
12.1.1. Un AFD es un tipo de autómata finito en el cual, para cada estado y símbolo de entrada, hay una única transición posible. No hay ambigüedad en la elección de la transición
12.2. Ejemplo:
12.2.1. un sistema de control para una puerta que solo puede estar abierta o cerrada. Si el sistema está en el estado "abierto" y se recibe el símbolo "cerrar", el sistema transitará al estado "cerrado".
12.3. Aplicación:
12.3.1. Protocolos de comunicación: Modelar el comportamiento de protocolos de comunicación en sistemas distribuidos, como el protocolo TCP en redes de computadoras. Análisis de cadenas de texto: Buscar patrones o palabras clave en documentos de texto o archivos, como en motores de búsqueda de texto. Verificación de sistemas: Verificación de sistemas para comprobar propiedades de sistemas de software y hardware.
13. Lenguajes Regulares (LR)
13.1. Definición:
13.1.1. Son aquellos que pueden ser modelados por autómatas finitos o expresados mediante patrones simples llamados "expresiones regulares".
13.2. Ejemplo:
13.2.1. Lenguaje d e cadenas binarias: {ε, 0, 1, 00, 01, 10, 11, ...} cadenas posibles formadas por los símbolos binarios 0 y 1. Lenguaje de números enteros: {0, 1, -1, 2, -2, 3, -3, ...} Contiene todos los números enteros positivos y negativos. Lenguaje de palíndromos: {ε, a, b, aa, bb, aba, bab, ...} se leen igual de izquierda a derecha que de derecha a izquierda
13.3. Aplicaciones:
13.3.1. Análisis léxico en compiladores Búsqueda y extracción de información: Utilizados en la búsqueda y extracción de información en archivos de texto y bases de datos. Validación de entradas: Los lenguajes regulares se emplean para validar entradas en formularios web o sistemas de entrada de datos, como direcciones de correo electrónico, números de teléfono y códigos postales. Diseño de patrones en redes y sistemas de búsqueda Análisis de texto y minería de datos: En el procesamiento de lenguaje natural y la minería de datos.
13.4. LR por Extensión: Es un conjunto de cadenas de caracteres que son especificadas explícitamente, es decir, enumerando todas las cadenas que forman parte del lenguaje. Cada cadena en el conjunto debe ser finita y estar compuesta por símbolos de un alfabeto dado.
13.4.1. Ejemplo:
13.4.1.1. El lenguaje que contiene todas las fechas en formato "dd/mm/yyyy": {01/01/2023, 03/12/2021, 07/25/2020, ...}
13.4.2. Aplicación:
13.4.2.1. En la verificación de sistemas En la especificación de casos de prueba
13.5. LR por Comprensión: se describe mediante una regla o una expresión que genera todas las cadenas que forman parte del lenguaje
13.5.1. Ejemplo:
13.5.1.1. El lenguaje que contiene todas las cadenas de texto formadas por la repetición de "a" seguida de la repetición de "b": {a^n b^n | n ≥ 0}
13.5.2. Aplicación:
13.5.2.1. En la especificación de gramáticas para el análisis sintáctico de lenguajes de programación y lenguajes naturales. En la descripción de patrones para el reconocimiento de tokens en análisis léxico de compiladores. En el diseño de sistemas de validación y filtrado de datos
13.6. Operación regulares : son acciones que se pueden aplicar a lenguajes regulares para crear nuevos lenguajes. Algunas de las operaciones más comunes son la unión, la concatenación, y la cerradura de Kleene.
13.6.1. Ejemplo
13.6.1.1. Supongamos que tenemos dos lenguajes: L1 = {a, aa, aaa} L2 = {b, bb} Unión (L1 ∪ L2): L1 ∪ L2 = {a, aa, aaa, b, bb} Concatenación (L1 · L2): L1 · L2 = {ab, aab, aaab, abb, aabb, aaaabb} Cerradura de Kleene (L1*): L1* = {ε, a, aa, aaa, aa...a, εa, aε, εaa, aεa, aaε, ...}
13.6.2. Aplicacion:
13.6.2.1. Análisis Léxico en Compiladores Búsqueda y Extracción de Información
13.6.3. OR Unión:La unión de dos lenguajes regulares L1 y L2, denotada como L1 ∪ L2, es el lenguaje que contiene todas las cadenas que pertenecen a L1 o a L2, o ambas.
13.6.3.1. Ejemplo:
13.6.3.1.1. Si L1 es el lenguaje de todas las cadenas de "a" y L2 es el lenguaje de todas las cadenas de "b", entonces L1 ∪ L2 sería el lenguaje de todas las cadenas de "a" o "b": L1 = {a, aa, aaa, ...} L2 = {b, bb, bbb, ...} L1 ∪ L2 = {a, aa, aaa, ..., b, bb, bbb, ...}
13.6.3.2. Aplicación:
13.6.3.2.1. La unión es útil en situaciones en las que se deben combinar lenguajes o conjuntos de cadenas para realizar búsquedas o manipulaciones conjuntas. Por ejemplo, al buscar patrones en un texto que pueden ser representados por diferentes lenguajes.
13.6.4. Cocatenación:La concatenación de dos lenguajes regulares L1 y L2, denotada como L1 · L2, es el lenguaje que contiene todas las cadenas que se pueden formar al tomar una cadena de L1 y otra de L2 y concatenarlas.
13.6.4.1. Ejemplo:
13.6.4.1.1. Si L1 es el lenguaje de todas las cadenas de "ab" y L2 es el lenguaje de todas las cadenas de "cd", entonces L1 · L2 sería el lenguaje de todas las cadenas de "abcd": L1 = {ab, abab, ababab, ...} L2 = {cd, cdcd, cdcdcd, ...} L1 · L2 = {abcd, ababcd, abababcd, ...}
13.6.4.2. Aplicación:
13.6.4.2.1. La concatenación se usa en la construcción de lenguajes más complejos a partir de componentes más simples. Por ejemplo, en el diseño de gramáticas para el análisis sintáctico de lenguajes de programación, donde las producciones se pueden concatenar para construir estructuras más complejas.
14. Automata Finito No Determinista
14.1. Definición:
14.1.1. Es un tipo de autómata finito en el cual, para un estado y un símbolo de entrada, puede haber múltiples transiciones posibles.
14.2. Ejemplo:
14.2.1. Representar las elecciones del jugador, ya que en un estado dado y con una entrada particular, podría haber múltiples opciones de transición, cada una llevando a un posible resultado diferente.
14.3. Aplicación:
14.3.1. Expresiones regulares: Base importante para las expresiones regulares, que se utilizan en la búsqueda y manipulación de patrones en cadenas de texto. Lenguajes formales: Modelar lenguajes formales y gramáticas, lo que es esencial para el procesamiento del lenguaje natural y la generación de analizadores sintácticos. Resolución de problemas de decisión: Se aplican en problemas de decisión donde se busca determinar si una determinada cadena es aceptada por un autómata, como en la resolución de problemas de satisfacción de restricciones.
15. Automata finito
15.1. Definición:
15.1.1. Es un modelo matemático que describe sistemas de cómputo con estados finitos. Tiene un conjunto de estados, un alfabeto de entrada, una función de transición y un conjunto de estados finales.
15.1.1.1. Estado: Un estado en un autómata representa una configuración o situación en la que se encuentra el sistema en un momento dado.
15.1.1.2. Transición: Una transición en un autómata define cómo cambia el estado del autómata cuando se lee un símbolo de entrada particular
15.2. Ejemplo:
15.2.1. Un semáforo que tiene tres luces: roja, amarilla y verde. Puedes modelar este semáforo como un autómata finito con tres estados (uno para cada luz) y transiciones que cambian de un estado a otro en función de si se enciende la luz roja, amarilla o verde.
15.3. Aplicacion:
15.3.1. Compiladores y análisis léxico: se utilizan en la fase de análisis léxico de un compilador para reconocer y tokenizar el código fuente en elementos como palabras clave, identificadores y operadores. Reconocimiento de patrones: Buscar patrones específicos en secuencias de entrada, como en la detección de secuencias de ADN en bioinformática. Control de estado: Son útiles para modelar sistemas de control con estados discretos, como semáforos, sistemas de control de tráfico y máquinas expendedoras.
16. Expresión regular
16.1. Definición:
16.1.1. es una secuencia de caracteres que define un patrón de búsqueda en una cadena de texto.
16.2. Ejemplo:
16.2.1. Búsqueda de direcciones de correo electrónico: Expresión regular: [a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,} Esta expresión busca patrones que se asemejen a direcciones de correo electrónico en un texto. Validación de números de teléfono: Expresión regular: ^\d{3}-\d{3}-\d{4}$ Esta expresión verifica si un número de teléfono tiene el formato xxx-xxx-xxxx.
16.3. Aplicación:
16.3.1. Análisis de texto y datos Validación de entradas Edición y manipulación de texto Procesamiento de lenguaje natural Extracción de datos web Compiladores y análisis léxico