Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Autómatas y lenguajes formales => Mensaje iniciado por: manooooh en 22 Febrero, 2018, 05:24 am

Título: Hallar lenguaje generado por una gramática regular
Publicado por: manooooh en 22 Febrero, 2018, 05:24 am
Hola a todos! No puedo resolver este ejercicio:

"Hallar el lenguaje generado por la gramática regular \( G=(\{S,A,B\},\{a,b\},P,S) \), con \( P \) dada por \( S\to\lambda/aB/bA,\; A\to bB,\; B\to bS \). Expresarlo mediante una expresión regular".



Es claro que va a generar un lenguaje infinito, pero al ir haciendo el árbol de derivación, con esas producciones, me cuesta ver el lenguaje generado. ¿Alguna ayuda?

Muchas gracias!
Saludos!
Título: Re: Hallar lenguaje generado por una gramática regular
Publicado por: geómetracat en 22 Febrero, 2018, 11:36 am
Tal vez te ayude observar que el lenguaje que genera esa gramática es el mismo que el que genera la gramática con sólo un símbolo inicial \( S \) y las reglas de producción: \( S \rightarrow \lambda | abS | bbbS \).
Título: Re: Hallar lenguaje generado por una gramática regular
Publicado por: manooooh en 22 Febrero, 2018, 05:51 pm
Hola

Tal vez te ayude observar que el lenguaje que genera esa gramática es el mismo que el que genera la gramática con sólo un símbolo inicial \( S \) y las reglas de producción: \( S \rightarrow \lambda | abS | bbbS \).

No sería \( S\to \lambda\to ab{\color{red}b}S\to bbbS \)?
Título: Re: Hallar lenguaje generado por una gramática regular
Publicado por: geómetracat en 23 Febrero, 2018, 05:00 pm
Hola

Tal vez te ayude observar que el lenguaje que genera esa gramática es el mismo que el que genera la gramática con sólo un símbolo inicial \( S \) y las reglas de producción: \( S \rightarrow \lambda | abS | bbbS \).

No sería \( S\to \lambda\to ab{\color{red}b}S\to bbbS \)?

Um, diría que la derivación es \( S \to aB \to abS \), ¿no?
Título: Re: Hallar lenguaje generado por una gramática regular
Publicado por: manooooh en 23 Febrero, 2018, 05:37 pm
Hola

Tal vez te ayude observar que el lenguaje que genera esa gramática es el mismo que el que genera la gramática con sólo un símbolo inicial \( S \) y las reglas de producción: \( S \rightarrow \lambda | abS | bbbS \).

No sería \( S\to \lambda\to ab{\color{red}b}S\to bbbS \)?

Um, diría que la derivación es \( S \to aB \to abS \), ¿no?

Cierto! Ya pude resolverlo geómetracat, gracias!

Saludos