Taller de Autómatas Gramaticales.

Taller I de Autómatas Gramaticales

1. Se tiene que A = {ξ, a}

1. Hallar Aᶯ para n = {0, 1, 2, 3}
2. Para un n cualquiera, ¿Cuántas palabras se generan?
3. Para un n cualquiera, ¿Cuáles son esas palabras?

1. Sea A = { ξ, ab}; B = {cd}

1. Hallar AᶯB para n = 0, 1, 2, 3.

Solución

1. Resolvemos:

1. A = {ξ, a}; n = {0, 1, 2, 3}

Aᶯ => A⁰ = {ξ}

             A¹ = {ξ, a}

             A² = {ξ, a}{ξ ,a} => A² = {ξ ,a, aa}

             A³ = A²A => {ξ, a, aa}{ξ ,a} => A³ = {ξ, a, aa, aaa}

1. Para un ‘n’ cualquiera la cantidad de palabras que se generan está dada por el valor de ‘n’, por ejemplo: para n=0, se generan 0 palabras; para n=3, se generan 3 palabras, para n=10 se generan 10 palabras.
2. Si queremos saber cuáles son las palabras que se generan para un ‘n’ cualquiera solo debemos hacer A*.

1. Resolvemos:

1. A = {ξ, ab}; B = {cd}; n = {0, 1, 2, 3}

AᶯB => A⁰B = {ξ}{cd} => A⁰B = {cd}

             A¹B = {ξ, ab}{cd} => A¹B = {cd, abcd}

             A²B = {ξ, ab}{ξ, ab}{ξ ,cd, abcd} => A²B = {cd, abcd, ababcd}

             A³B = A²AB => {ξ, ab, abab}{ξ ,ab}{cd} => A³B = {cd, abcd, ababcd, abababcd}

1. Expresión regular

Una expresión regular, a menudo llamada también regex, es una secuencia de caracteres que forma un patrón de búsqueda, principalmente utilizada para la búsqueda de patrones de cadenas de caracteres u operaciones de sustituciones. Por ejemplo, el grupo formado por las cadenas Handel, Händel y Haendel se describe con el patrón "H(a|ä|ae)ndel". La mayoría de las formalizaciones proporcionan los siguientes constructores: una expresión regular es una forma de representar a los lenguajes regulares (finitos o infinitos) y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje.

En informática, las expresiones regulares proveen una manera muy flexible de buscar o reconocer cadenas de texto.

Construcción de expresiones regulares

Específicamente, las expresiones regulares se construyen utilizando los operadores unión, concatenación y clausura de Kleene. Toda expresión regular tiene algún autómata finito asociado.

Alternación: Una barra vertical separa las alternativas. Por ejemplo, "marrón|castaño" se corresponde con marrón o castaño.

Cuantificación: Un cuantificador tras un carácter especifica la frecuencia con la que éste puede ocurrir. Los cuantificadores más comunes son ?, + y *:

...