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

• ? El signo de interrogación indica que el carácter que le precede puede aparecer como mucho una vez. Por ejemplo, "ob?scuro" se corresponde con oscuro y obscuro.
• + El signo más indica que el carácter que le precede debe aparecer al menos una vez. Por ejemplo, "ho+la" describe el conjunto infinito hola, hoola, hooola,hoooola, etcétera.
• * El asterisco indica que el carácter que le precede puede aparecer cero, una, o más veces. Por ejemplo, "0*42" se corresponde con 42, 042, 0042, 00042, etcétera.

Agrupación: Los paréntesis pueden usarse para definir el ámbito y precedencia de los demás operadores. Por ejemplo, "(p|m)adre" es lo mismo que "padre|madre", y "(des)?amor" se corresponde con amor y con desamor.

Los constructores pueden combinarse libremente dentro de la misma expresión, por lo que "H(ae?|ä)ndel" equivale a "H(a|ae|ä)ndel".

La sintaxis precisa de las expresiones regulares cambia según las herramientas y aplicaciones consideradas, y se describe con más detalle a continuación.

Aplicaciones

...