LENGUAJES Y AUTOMATAS 1

2.1. Definición formal de una ER. Es un equivalente algebraico para un autómata. Utilizado en muchos lugares como un lenguaje para describir patrones en texto que son sencillos pero muy útiles. Pueden definir exactamente los mismos lenguajes que los autómatas pueden describir: Lenguajes regulares. Ofrecen algo que los autómatas no: Manera declarativa de expresar las cadenas que queremos aceptar. Dado un alfabeto Dado un alfabeto Σ, una , expresión regular sobre expresión regular sobre Σ se define de forma recursiva: ER primitivas:  Φ , λ, {a | a  ЄЄЄ  Σ  Є } Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α). No existen otras reglas para la construcción de ER sobre Σ. Ejemplos de usos. Comandos de búsqueda, e.g., grep de UNIX. sistema de formato de texto: Usan notación de tipo expresión regular para describir patrones. Convierte la expresión regular a un DFA o un NFA y simula el autómata en el ar...

1.1    Alfabeto Un alfabeto es un conjunto finito no vacío cuyos elementos se llaman símbolos. Denotamos un alfabeto arbitrario con la letra Σ. Símbolos: Es una entidad abstracta que no se puede definir, ya que se dejaría como una axioma. Igual que se define un punto en la geometría. La cual normalmente los símbolos son letras (a, b, c,…. z), dígitos (0,1,…9, caracteres (+, -, *, /,>,< …..). los símbolos pueden estar formados por varias letras o caracteres. Alfabeto: El alfabeto o abecedario es un conjunto de letras, con un determinado orden. podríamos precisamente decir que el alfabeto es un conjunto de letras (caracteres o grafemas) de un sistema de escritura, cada una representa aproximadamente un fonema (consonante o vocal). 1.2 Cadenas. Una cadena o palabra sobre un alfabeto Σ. admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ. la cadena vacía desempeña, en la teoría de lenguajes ...