• Author / Uploaded
• Winston Ferreira

Citation preview

Ejercicios CFG Winston Ferreira Delgado 01 de diciembre de 2020 1. Se trabajar´a simpre con el alfabeto Σ = {a, b, c}. Encontrar una GFG que genere el lenguaje propuesto. 5) {ai bj aj+1 bi+1 |i, j ∈ N} 2. Se trabajar´a simpre con el alfabeto Σ = {a, b, c}. Encontrar una GFG que genere el lenguaje propuesto. 4) {ai wbi |w ∈ Σ∗ ∧ i ∈ N ∧ wR = w} 3. Se trabajar´a simpre con el alfabeto Σ = {a, b, c}. Encontrar una Gram´atica Regular que genere el lenguaje propuesto. 2) {w ∈ Σ∗ | |w|a ≡ |w|b + |w|c (mod 2)} ´ SOLUCION 1. {ai bj aj+1 bi+1 |i, j ∈ N}Σ Dado que la cantidad de a’s y b’s en los extremos de la palabra est´an condicionadas por la variable i y la cantidad de a0 s y b0 s del medio de la palabra est´an condicionadas por la variable j por lo tanto se trabajar´an en dos funciones separadas. Primero partimos por una S y esa funci´on hace que S −→ aSb Para que la cantidad de a’s y b’s en los extremos de la palabra sean los mismos, pero como la cantidad no es la misma sino que la cantidad de a0 s es igual a i y la cantidad de b0 s es igual a i + 1, entonces tambi´en le agregamos S −→ Ab Para que al final cambie de funci´on a la que nos va a permitir ingresar las letras del medio de la palabra y que la cantidad de a’s y b’s en los 1

extremos sean los correspondientes. Ahora para la definir la funci´on A usamos un razonamiento an´alogo de modo que la funci´on A sea A −→ bAa As´ı la cantidad de a0 s y b0 s en el centro de la palabra sean iguales, pero similar a la anterior funci´on la cantidad de b0 s es igual a i y la cantidad de a0 s es igual a i + 1, pero como a diferencia de la anterior funci´on no cambiamos a otra funci´on, sino que damos por terminada la palabra, entonces tambi´en A hace que A −→ λa Ahora por ultimo unimos las diferentes opciones que pueden hacer las dos funciones de modo que el CFG quede de la siguiente forma: S −→ aSb | Ab A −→ bAa | λa 2. {ai wbi |w ∈ Σ∗ ∧ i ∈ N ∧ wR = w} Similar al ejercicio anterior vamos a usar 2 funciones, la primera para hacer las a0 s y b0 s de los extremos y la segunda para hacer la palabra w para que sea pal´ındromo, entonces la primera parte la funci´on S va a hacer la operaci´on S −→ aSb Pero la funci´on S tambi´en puede pasar a la siguiente funci´on en cualquier momento, por lo tanto, la funci´on tambi´en har´a la operaci´on S −→ A Ahora para definir la funci´on A necesitamos crear un pal´ındromo, por lo tanto, la funci´on en el momento de colocar una a a a la derecha, tambi´en necesitaremos una a a la izquierda, y lo mismo al colocar alguna b, por eso la funci´on A har´a las operaciones A −→ aAa | bAb Pero dado que no solo son los pal´ındromos de tama˜ no par, por eso al momento de terminar la palabra que va a ser en el centro de w podremos colocar una u ´ltima a o una u ´ltima b, pero tambi´en finalizar la palabra w con tama˜ no par colocando u ´nicamente λ al finalizar la palabra, entonces A tambi´en podr´a hacer las operaciones A −→ aλ | bλ | λ 2

Por ultimo para escribir el CFG unimos todas las posibles operaciones que pueden hacer las funciones de modo que quede as´ı: S −→ aSb | A A −→ aAa | bAb | aλ | bλ | λ 3. {w ∈ Σ∗ | |w|a ≡ |w|b + |w|c (mod 2)} Como el modulo que el ejercicio nos plantea es mod 2, entonces solo hay 2 posibles estados para |w|a que son |w|a = 2n o |w|a = 2n+1 y as´ı mismo para |w|b +|w|c los cuales son 2n y 2n + 1 y que al agregar un a en el primer caso o b o c en el segundo caso, estos cambiaran de estado 2n a 2n+1 o viceversa. Como el estado de los dos casos deben ser los mismos para que la palabra este en estado de aceptaci´on, entonces si suponemos que la palabra est´a en estado de aceptaci´on, entonces basta con agregar a la palabra de longitud 2 para que siga en estado de aceptaci´on. Ahora que sabemos eso, creamos un lenguaje regular que de todas las posibles combinaciones de longitud 2 con {a, b, c}, y ese lenguaje es (a ∨ b ∨ c)(a ∨ b ∨ c) Ahora solo basta con concatenar muchas veces esas palabras de longitud 2 con λ y ellas mismas, y para esto usamos la estrella de Kleene, lo cual sigue siendo lenguaje regular, por lo tanto, la soluci´on de este ejercicio es: [(a ∨ b ∨ c)(a ∨ b ∨ c)]∗

3