Así que estaba tratando de resolver el CFG,
$$\{w \in (0,1)^* \mid w \text{ contains at least three 1's}\}$$
Mi enfoque:
Decidí que una cadena puede comenzar con un $0$ , terminar con un $0$ puede comenzar con un $1$ , terminó con un $1$ , comienzan con un 0 y terminan con un $1$ o comenzar con un $1$ y terminar con un $0$ .
Esto culmina en:
$S \to 0S0 \mid 1S0 \mid 0S1 \mid 1S1 \mid 111$
Esto es regular, por lo que una gramática es simple de cocinar a partir de un DFA. Sea $A$ no se puede defender a nadie todavía, $B$ para uno 1, $C$ para dos 1, y $D$ para tres (o más) 1. Entonces: $$ \begin{align*} A &\rightarrow 0 A \mid 1 B \\ B &\rightarrow 0 B \mid 1 C \\ C &\rightarrow 0 C \mid 1 D \mid 1 \\ D &\rightarrow 0 D \mid 1 D \mid 0 \mid 1 \end{align*} $$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Su gramática propuesta parece producir el conjunto de todas las cadenas de longitud impar que contengan al menos tres consecutivo 1 en el centro de la cadena.
0 votos
@AndreasBlass ¿cómo podría modificarlo para que funcione para todas las longitudes?
1 votos
¿Querías decir $w \in \{0,1\}^*$ ? Si es así, basta con una expresión regular, por ejemplo $\Sigma^*(1\Sigma^*)^3$ para $\Sigma = \{0,1\}$ .