Automatas y lenguejes formales
Alfabeto
Un alfabeto es un conjunto finito de símbolos, dichos símbolos son los bloques fundamentales a partir de los cuales se construyen las palabras o cadenas en un lenguaje.
Un alfabeto es un conjunto finito de símbolos, dichos símbolos son los bloques fundamentales a partir de los cuales se construyen las palabras o cadenas en un lenguaje.
Aplicación: En criptografía, los alfabetos se utilizan para representar los caracteres que se cifran o descifran en sistemas de cifrado.
Ejemplo: El alfabeto latino Σ = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘, 𝑙, 𝑚, 𝑛, 𝑜, 𝑝, 𝑞, 𝑟, 𝑠, 𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦, 𝑧},
Ejemplo: En el alfabeto {0, 1}, el tamaño es 2. En el alfabeto {𝑎, 𝑏, 𝑐}, el tamaño es 3.
Aplicación: En la creación de gramáticas, análisis léxicos y en sistemas de codificación.
Aplicación: En la creación de gramáticas, análisis léxicos y en sistemas de codificación.
Ejemplo: En el alfabeto {0, 1}, los símbolos son 0 y 1. En el alfabeto {a, b, c}, los símbolos son a, b y c.
Ejemplo: tenemos el alfabeto {a, b}, algunas posibles cadenas podrían ser "aababa", "bbba", etc.
Aplicación: En documentos legales, las palabras representan cláusulas, nombres de partes involucradas y otros detalles.
Ejemplo: código binario 0011,01100,011000
Aplicación: validaciones de datos, como direcciones de correo electrónico válidas
Ejemplo: L = {"a", "ab", "abc", "abcd"}
En este ejemplo, el lenguaje L contiene solo cuatro cadenas, lo que lo convierte en un lenguaje finito.
Aplicación: En el diseño de juegos, los lenguajes finitos pueden representar acciones, decisiones y eventos en el juego
Ejemplo: 𝐿 = {"a", "aa", "aaa", "aaaa", …}
En este ejemplo, el lenguaje L contiene cadenas de "a" de longitud creciente, lo que resulta en un lenguaje infinito.
Aplicación: En simulaciones de sistemas físicos y fenómenos naturales.
Ejemplo: Un elevador, ya que es capaz de memorizar las diferentes llamadas de cada piso y optimizar sus ascensos y descensos.
Aplicación: En los diseños de videojuegos, los autómatas finitos pueden usarse para modelar el comportamiento de personajes y enemigo.
Ejemplo: para la entrada "00101", el autómata seguiría estos pasos:
𝑞0 (𝑒𝑠𝑡𝑎𝑑𝑜 𝑖𝑛𝑖𝑐𝑖𝑎𝑙) − "0" −> 𝑞1
𝑞1 − "0" −> 𝑞0
𝑞0 − "1" −> 𝑞0
𝑞0 − "0" −> 𝑞1
𝑞1 − "1" −> 𝑞1
La cadena se rechazaría porque al final el autómata está en el estado 𝑞1, y el número de 0 (2) no es par.
Aplicación: En los modelado de protocolos de comunicaciones y redes, para describir protocolos y comportamientos predecibles de sistemas de comunicación
Ejemplo: Sea entonces 𝑀 un AFN, tal que 𝑀= { 𝑆, Σ, Δ, 𝑠0, 𝐹}
Donde:
𝑆= { 0, 1, 2, 3}
Σ= { 𝑎, 𝑏}
Δ= { { 0, 𝑎, { 0, 1}}, { 0, 𝑏, { 0}}, { 1, 𝑏, { 2}}, { 2,
𝑏, { 3}}}
𝑠0= { 0}
𝐹= { 3}
Aplicación: En la modelización de sistemas complejos, permiten manejar múltiples estados y posibles interacciones
Ejemplo: 𝐷𝑎𝑑𝑜 Σ = {𝑎,𝑏}, las siguientes
afirmaciones son ciertas:
𝜑 𝑦 {𝜀} son lenguajes regulares
{𝑎} y {𝑏} son lenguajes regulares
{𝑎, 𝑏} es un lenguaje regular
{𝑎𝑏} es un lenguaje regular
{𝑎, 𝑎𝑏, 𝑏} es un lenguaje regular
{𝑎^𝑖 | 𝑖 ≥ 0} es un lenguaje regular
{𝑎^𝑖 𝑏^𝑗 | 𝑖 ≥ 0 𝑦 𝑗 ≥ 0} es un lenguaje regular
{(𝑎𝑏)^𝑖 | 𝑖 ≥ 0} es un lenguaje regular
Aplicación: En la detección y análisis de patrones en tráfico de red y protocolos de comunicación.
Ejemplo: 01∗ + 10∗ denota todas las cadenas que son o un 0 seguido de cualquier cantidad de 1’s o un 1 seguida de cualquier cantidad de 0’s.
Aplicación: En procesamiento de texto y análisis de datos, están ayudan a extraer información específica de documentos
Ejemplo: Lenguaje de cadenas binarias con una cantidad par de 1s: {w | w contiene una cantidad par de 1s}.
Este lenguaje contiene todas las cadenas binarias que tienen una cantidad par de símbolos "1", incluyen "010", "1100", "0011", etc.
^
Aplicación: En lenguajes de marcado como HTML y XML, se usan para analizar y manipular contenido estructurado
Ejemplo: Lenguaje de números pares menores a 10: {0, 2, 4, 6, 8}
En este caso, el lenguaje contiene todos los números pares menores que 10.
Aplicación: En lenguajes de marcado como HTML y XML, se usan para analizar y manipular contenido estructurado
Ejemplo:
q0: Representa que la cadena actual es un múltiplo de tres (congruencia 0).
q1: Representa que la cadena actual es un múltiplo de tres más uno (congruencia 1).
Aplicación: En sistemas de control automático, los estados representan las condiciones del sistema y se utilizan para tomar decisiones y ajustar parámetros.
Ejemplo: Conjunto de estados: {𝑞0, 𝑞1, 𝑞2}
Alfabeto: {0, 1}
Estado inicial: 𝑞0
Estado de aceptación: 𝑞0
Reglas de transición:
𝛿(𝑞0, 0) = 𝑞0
𝛿(𝑞0, 1) = 𝑞1
𝛿(𝑞1, 0) = 𝑞2
𝛿(𝑞1, 1) = 𝑞0
𝛿(𝑞2, 0) = 𝑞1
𝛿(𝑞2, 1) = 𝑞2
Aplicación: las transiciones pueden representar cómo un robot cambia su comportamiento en función de los sensores y las acciones realizadas.
Ejemplo: Tenemos una cadena de caracteres del lenguaje de programación C.char str[12]= “bienvenidos”; donde char es la variable de caracteres y str de cadena. La cadena de caracteres es bienvenidos.
Aplicación: En matemáticas se emplean para representar relaciones, operaciones y fórmulas y en la informática los lenguajes formales constituyen la base para la definición de los lenguajes de programación.
^
Ejemplo: Supongamos que tenemos dos lenguajes regulares: 𝐿1 = {𝑧, 𝑧𝑧} 𝑦 𝐿2 = {𝑥, 𝑥𝑥}. A continuación, aplicamos las operaciones regulares:
Unión (U): 𝐿1 𝑈 𝐿2 = {𝑧, 𝑧𝑧, 𝑥, 𝑥𝑥}
Concatenación (·): 𝐿1 · 𝐿2 = {𝑧𝑥, 𝑧𝑥𝑥, 𝑧𝑧𝑥, 𝑧𝑧𝑧𝑥𝑥}
Estrella de Kleene (∗): 𝐿1∗ = {𝜀, 𝑧, 𝑧𝑧, 𝑧𝑧𝑧, …} (todas las posibles combinaciones de cadenas de L1, incluyendo la cadena vacía).
Ejemplo:
(.) (punto): Concatenación de símbolos.
(|) (barra vertical): Unión de expresiones.
Aplicación: En la optimización de código fuente, para simplificar y mejorar la eficiencia de las instrucciones y estructuras en un programa.
Ejemplo: En una expresión matemática
3 + 5 * 2
3+10=13
Aplicación: En sistemas de matemáticas simbólicas y en los lenguajes de programación.