[lindtaylor]

Hola.
Dado \( A=\left\{a,b\right\} \) alfabeto. ¿Cómo puedo definir el conjunto de todas las palabras (cadenas) tal que contienen la misma cantidad de letras \( a \) y letras \( b \)?


Como ejemplo por si  en el foro se usa otra notación, para describir el conjunto \( L \) de todas las palabras que contienen a la palabra \( aa \), tengo que es: \( L=L((a\vee b)^{\ast}aa(a\vee b)^{\ast})=A^{\ast}\left\{aa\right\}A^{\ast} \) con \( A^{\ast} \) el conjunto de todas las palabras sobre \( A \)


 

[lindtaylor]

Tengo la siguiente idea:

\( ((ab)^{\ast}\vee (ba)^{\ast}
\vee
(aabb)^{\ast}\vee (bbaa)^{\ast}
\vee
(aaabbb)^{\ast}\vee (bbbaaa)^{\ast}
\vee
\ldots )^{\ast} \)

Como conjunto, \( \left\{(a^nb^n)\vee (b^na^n): n\in\mathbb{N}\right\} \) (no sé si esté bien escrito el lenguaje pero la idea es lo que interesa.

Este conjunto me entrega siempre palabras con la misma cantidad de a's y b's.

¿Estaría bien? pues leí en una parte que \( (a^nb^n) \) (así tal cual) no es una expresión regular)

[manooooh]

Hola

¿Estaría bien? pues leí en una parte que \( (a^nb^n) \) (así tal cual) no es una expresión regular)

Desde mi punto de vista está perfecto \( \left\{(a^nb^n)\vee (b^na^n): n\in\mathbb{N}\right\}\equiv\left\{(a^nb^n)+(b^na^n): n\in\mathbb{N}\right\} \). ¿De dónde leíste que no es una expresión regular?

Saludos

[lindtaylor]

https://stackoverflow.com/questions/2309752/why-is-anbn-n-0-not-regular

[manooooh]

https://stackoverflow.com/questions/2309752/why-is-anbn-n-0-not-regular

Mmmm... es cierto. Pensé como vos en \( \{(ab)^\ast\vee(ba)^\ast\} \) (no veo por qué está mal). Si lo está no sé cómo ayudarte, quizás me venga una idea después.

Saludos