Automatas y lenguejes formales

Mais informações

La función del estado en la economía Peruana

por Arian Job

LOS DERECHOS SOCIALES

por Julian Felipe Portillo

EL ARTE EN LA EDUCACIÓN INICIAL

por Didier Parra

Estrategia del Servicio

por ALEX DURAN

Precedencia de los operadores

Conjunto de reglas que establecen el orden en que se evalúan o aplican los operadores en una expresión.

Aplicación: En sistemas de matemáticas simbólicas y en los lenguajes de programación.

Ejemplo: En una expresión matemática 3 + 5 * 2 3+10=13

Operador

Conjunto de símbolos que denota una operación o acción específica en una expresión o lenguaje formal.

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: (.) (punto): Concatenación de símbolos. (|) (barra vertical): Unión de expresiones.

Aplicación: en el procesamiento de texto, para buscar, filtrar y reemplazar patrones específicos en documentos o cadenas

Operaciones regulares

Unión: Combinación de dos lenguajes para formar un nuevo lenguaje que contiene todas las cadenas que pertenecen a al menos uno de los lenguajes originales.

Concatenación: La combinación de dos cadenas para formar una nueva cadena.

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

Estrella de Kleene: Es el conjunto de todas las cadenas que se pueden obtener al concatenar cualquier número de cadenas.

Gramática formal

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

Transición

Se definen cómo un autómata se mueve de un estado a otro en respuesta a un símbolo de entrada.

Aplicación: las transiciones pueden representar cómo un robot cambia su comportamiento en función de los sensores y las acciones realizadas.

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

Estado

Es una configuración en la que se encuentra el autómata en un momento dado. Sirve como una representación interna que muestra cómo está avanzando en el procesamiento de la entrada

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

Lenguaje regular

Extensiones: Enumerar explícitamente todos los elementos que pertenecen a ese lenguaje.

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.

Comprensión: Regla o patrón que describe las propiedades que deben cumplir las cadenas para pertenecer al lenguaje.

Aplicación: En lenguajes de marcado como HTML y XML, se usan para analizar y manipular contenido estructurado

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.

Expresión regular:

Es un tipo de lenguaje formal que puede ser descrito o definido mediante expresiones regulares, autómatas finitos o gramáticas regulares.

Aplicación: En procesamiento de texto y análisis de datos, están ayudan a extraer información específica de documentos

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.

Lenguaje regular

Conjunto de cadenas que puede ser reconocido por un autómata finito, y que puede ser descrito por expresiones regulares.

Aplicación: En la detección y análisis de patrones en tráfico de red y protocolos de comunicación.

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

Autómata No Finito Determinista

Es un conjunto finito de estados y opera en función de una entrada siguiendo reglas de transición que permiten múltiples opciones de cambio de estado para un mismo símbolo de entrada en un estado dado.

Aplicación: En la modelización de sistemas complejos, permiten manejar múltiples estados y posibles interacciones

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}

Autómata Finito Determinista

Es un modelo teórico de una máquina que tiene un conjunto finito de estados y opera en función de una entrada siguiendo reglas de transición deterministas

Aplicación: En los modelado de protocolos de comunicaciones y redes, para describir protocolos y comportamientos predecibles de sistemas de comunicación

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.

Autómata Finito

Es un modelo teórico de una máquina con estados limitados que cambia de estado según una entrada

Aplicación: En los diseños de videojuegos, los autómatas finitos pueden usarse para modelar el comportamiento de personajes y enemigo.

Ejemplo: Un elevador, ya que es capaz de memorizar las diferentes llamadas de cada piso y optimizar sus ascensos y descensos.

Subconceptos Lenguaje

Lenguajes infinitos: Conjunto de cadenas que tiene una cantidad infinita de elementos.

Aplicación: En simulaciones de sistemas físicos y fenómenos naturales.

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.

Lenguajes finitos: Conjunto de cadenas que contiene una cantidad finita de elementos, donde cada elemento está compuesto por símbolos tomados de un alfabeto específico.

Aplicación: En el diseño de juegos, los lenguajes finitos pueden representar acciones, decisiones y eventos en el juego

Ejemplo: L = {"a", "ab", "abc", "abcd"} En este ejemplo, el lenguaje L contiene solo cuatro cadenas, lo que lo convierte en un lenguaje finito.

Lenguaje

Un lenguaje es un conjunto de cadenas formadas por símbolos de un alfabeto específico, estos lenguajes puede ser finitos o infinitos

Aplicación: validaciones de datos, como direcciones de correo electrónico válidas

Ejemplo: código binario 0011,01100,011000

Palabra o Cadena

Es una expresión conformada por símbolos del alfabeto.

Aplicación: En documentos legales, las palabras representan cláusulas, nombres de partes involucradas y otros detalles.

Ejemplo: tenemos el alfabeto {a, b}, algunas posibles cadenas podrían ser "aababa", "bbba", etc.

Subconceptos Alfabeto

Alfabeto y Símbolos: Un alfabeto es un conjunto de símbolos que se utilizan para formar cadenas en un lenguaje. Los símbolos son elementos básicos que pueden ser letras, números u otros caracteres individuales.

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.

Tamaño y Cardinalidad: El tamaño del alfabeto se refiere al número total de símbolos que contiene. Puede ser finito, con un número específico de símbolos, o infinito si tiene una cantidad ilimitada.

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}, el tamaño es 2. En el alfabeto {𝑎, 𝑏, 𝑐}, el tamaño es 3.

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.

Ejemplo: El alfabeto latino Σ = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘, 𝑙, 𝑚, 𝑛, 𝑜, 𝑝, 𝑞, 𝑟, 𝑠, 𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦, 𝑧},

Aplicación: En criptografía, los alfabetos se utilizan para representar los caracteres que se cifran o descifran en sistemas de cifrado.