lenguajes generados por gramáticas expresadas con expresiones regulares formales

[juyo]

¿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 a^mbⁿ 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∗)

[Alex Rodríguez]

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