Hola a todos! Tengo una pequeña duda sobre cómo generar lenguajes. El enunciado es:
"Sea \( G = \left(\{a, b\}, \; \{0, 1\}, \; P, a\right) \) una gramática con \( P: \begin{cases}a \rightarrow{} b0 / 0 \\ a0 \rightarrow{} b1 \\ b \rightarrow{} 1a / bb / 1 \\ a1 \rightarrow{} \lambda \textrm{ (palabra nula)} \end{cases} \) Hallar algunas palabras del lenguaje generado por \( G \)".
Empiezo por el elemento inicial (\( a \)) y aplico las producciones:
\( \begin{array}{llllll} a & \rightarrow{} & 0 \in{} L(G)\\ & \searrow{} & b0 & \rightarrow{} & 10 \in{} L(G) \\ & & & \searrow{} & 1a0 & \rightarrow{} & 100 \in{} L(G) \\ & & & & & \color{red}\searrow{} & \color{red}1b00 & \color{red}\rightarrow{} & \color{red}11000 \in{} L(G) \\ & & & & & & & \color{red}\searrow{} & \color{red}11a00 & \color{red}\rightarrow{} & \color{red}\ldots \end{array} \)
Mi duda es lo que está en rojo. Una vez que "producí" y llegué a un elemento terminal (\( 100 \)), ¿tengo que seguir con las otras opciones? Porque en este caso generé del \( 1a0 \) al \( 100 \) pues \( a \) puede tomar el valor \( 0 \)... pero también el elemento \( b0 \). En tal caso hay infinitas producciones, pero sino sería finita la cantidad. ¿Cómo es ésto?
Gracias!!
Nota: obviamente me faltan muchas más, incluida la palabra \( b0 \); sólo tomé el valor \( 1 \), pero también me faltan \( 1a \) y \( bb \) porque no son terminales.
