Autor Tema: lenguajes generados por gramáticas expresadas con expresiones regulares formales  (Leído 2174 veces)

juyo

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 1
    • Ver Perfil
¿Cuál de las siguientes gramáticas genera el lenguaje de todas las cadenas de {a, b} excepto las cadenas que tienen como subcadena la cadena ambn donde m, n > 0?

1) (a∗|b∗)(ba)∗(a∗|b∗)(b∗a∗)
2) a∗|b∗a∗|b∗|b∗(ba)∗a∗
3) b∗a∗
4) (ba)∗|(b∗|a∗)
« Última modificación: 03 de Septiembre 2019, 17:34 por Alex Rodríguez »

Alex Rodríguez

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2052
    • Ver Perfil
Re:lenguajes
« Respuesta #1 en: 03 de Septiembre 2019, 17:33 »
Hola, este foro no es es el adecuado para esta consulta, ya que este foro va dirigido a presentarse a la comunidad. Por ello, procederé a cambiar la consulta de foro Tampoco tiene un título adecuado, que debe ponerse siguiendo las indicaciones que hay en
https://aprenderaprogramar.com/foros/index.php?topic=1460.0 , por ello procederé a cambiarle el título. Tenlo en cuenta para futuras ocasiones por favor.

Tal y como entiendo la pregunta se refiere a todas las subcadenas que se pueden formar con a, b excepto las que contengan cualquier cadena tipo ab, aab, abb, aabb, es decir, no pueden contener as seguidas de bs.

Analizando las opciones:

La opción 1) admite aba por tanto sería falsa

La opción 2) admite aaaaa... , bbbbbbbb...aaaaaaaa, bbbbbbb...bababababa....aaaaaaaa... aquí la concatenación de ba genera bababababa dentro de la cual tenemos ab, por tanto sería falsa.

La opción 3) comprende bbbbb...aaaaaaaa

La opción 4 incluye babababa y en la concatenación tenemos ab por lo tanto sería falsa.

Lo que nos exige el enunciado es que:

- Una cadena no puede admitir una a antes de una b. Esto lo cumple la opción 3.
- Una cadena puede contener cualquier número de bs seguido de cualquier número de as. Esto lo cumple la opción 3.

La respuesta, salvo que me equivoque en algo, sería la opción 3)

Saludos

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".