$w$ de manera que contenga al menos 3 unos, ¿es correcto mi planteamiento de la CFG?

Question

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$

Answer 1

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*}$$

Answer 2

Espero que esto funcione:

$$S \implies S_1aS_1aS_1aS_1$$ $$S_1 \implies aS_1 | bS_1 | \epsilon$$

¿Cómo se ve esto?