Proponer una CFG para la expresion regular 0*1(0+1)* y derivar cadenas

La expresion regular $0^*1(0+1)^*$ describe cadenas que empiezan con cero o mas ceros, luego tienen exactamente un $1$, y despues cualquier combinacion de $0$‘s y $1$‘s. Para convertirla en gramatica, simplemente asignamos un no terminal a cada parte: $A$ genera los ceros iniciales ($0^*$), $B$ genera el $1$ obligatorio seguido del resto ($1(0+1)^*$), y $C$ genera la cola libre ($(0+1)^*$). La produccion inicial $S \to AB$ las conecta.

Las reglas quedan: $A \to 0A \mid \varepsilon$ (cero o mas ceros), $B \to 1C$ (el uno obligatorio), $C \to 0C \mid 1C \mid \varepsilon$ (cualquier sufijo binario). Para derivar una cadena concreta, se aplican las reglas de izquierda a derecha: primero se decide cuantos ceros pone $A$, luego $B$ coloca el $1$, y finalmente $C$ va generando los simbolos del sufijo uno por uno.

Por ejemplo, para $0110$: $S \Rightarrow AB \Rightarrow 0AB \Rightarrow 0B \Rightarrow 01C \Rightarrow 011C \Rightarrow 0110C \Rightarrow 0110$. Cada cadena de la tabla se obtiene de forma similar, eligiendo cuantas veces aplicar cada regla recursiva.

CFG $G = (\{S, A, B, C\},\ \{0, 1\},\ P,\ S)$ con:

$$\begin{aligned} S &\to AB \\ A &\to 0A \mid \varepsilon \\ B &\to 1C \\ C &\to 0C \mid 1C \mid \varepsilon \end{aligned}$$

Derivaciones:

Cadena	Reglas aplicadas
$1$	$S \to AB,\ A \to \varepsilon,\ B \to 1C,\ C \to \varepsilon$
$01$	$S \to AB,\ A \to 0A,\ A \to \varepsilon,\ B \to 1C,\ C \to \varepsilon$
$0110$	$S \to AB,\ A \to 0A,\ A \to \varepsilon,\ B \to 1C,\ C \to 1C,\ C \to 0C,\ C \to \varepsilon$
$00100$	$S \to AB,\ A \to 0A,\ A \to 0A,\ A \to \varepsilon,\ B \to 1C,\ C \to 0C,\ C \to 0C,\ C \to \varepsilon$
$101$	$S \to AB,\ A \to \varepsilon,\ B \to 1C,\ C \to 0C,\ C \to 1C,\ C \to \varepsilon$
$10111$	$S \to AB,\ A \to \varepsilon,\ B \to 1C,\ C \to 0C,\ C \to 1C,\ C \to 1C,\ C \to 1C,\ C \to \varepsilon$
$011$	$S \to AB,\ A \to 0A,\ A \to \varepsilon,\ B \to 1C,\ C \to 1C,\ C \to \varepsilon$

Gramatica

Solucion

Analisis de la expresion regular

La expresion regular $0^*1(0 + 1)^*$ describe cadenas que:

1. Empiezan con cero o mas $0$‘s
2. Seguidas de exactamente un $1$
3. Seguidas de cualquier combinacion de $0$‘s y $1$‘s

Gramatica libre de contexto

$$\begin{aligned} S &\to AB \\ A &\to 0A \mid \varepsilon \\ B &\to 1C \\ C &\to 0C \mid 1C \mid \varepsilon \end{aligned}$$

Donde:

• $A$ genera $0^*$ (cero o mas ceros)
• $B$ genera $1(0+1)^*$ (un $1$ seguido de cualquier cadena)
• $C$ genera $(0+1)^*$ (cualquier cadena binaria)

Derivaciones para cada cadena

Cadena $1$:

$S \Rightarrow AB \Rightarrow B \Rightarrow 1C \Rightarrow 1$

Reglas: $S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to \varepsilon$

Cadena $01$:

$S \Rightarrow AB \Rightarrow 0AB \Rightarrow 0B \Rightarrow 01C \Rightarrow 01$

Reglas: $S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to \varepsilon$

Cadena $0110$:

$S \Rightarrow AB \Rightarrow 0AB \Rightarrow 0B \Rightarrow 01C \Rightarrow 011C \Rightarrow 0110C \Rightarrow 0110$

Reglas: $S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 1C$, $C \to 0C$, $C \to \varepsilon$

Cadena $00100$:

$S \Rightarrow AB \Rightarrow 0AB \Rightarrow 00AB \Rightarrow 00B \Rightarrow 001C \Rightarrow 0010C \Rightarrow 00100C \Rightarrow 00100$

Reglas: $S \to AB$, $A \to 0A$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 0C$, $C \to \varepsilon$

Cadena $101$:

$S \Rightarrow AB \Rightarrow B \Rightarrow 1C \Rightarrow 10C \Rightarrow 101C \Rightarrow 101$

Reglas: $S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 1C$, $C \to \varepsilon$

Cadena $10111$:

$S \Rightarrow AB \Rightarrow B \Rightarrow 1C \Rightarrow 10C \Rightarrow 101C \Rightarrow 1011C \Rightarrow 10111C \Rightarrow 10111$

Reglas: $S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 1C$, $C \to 1C$, $C \to 1C$, $C \to \varepsilon$

Cadena $011$:

$S \Rightarrow AB \Rightarrow 0AB \Rightarrow 0B \Rightarrow 01C \Rightarrow 011C \Rightarrow 011$

Reglas: $S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 1C$, $C \to \varepsilon$

Tabla resumen

Generar	Reglas aplicadas
$1$	$S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to \varepsilon$
$01$	$S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to \varepsilon$
$0110$	$S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 1C$, $C \to 0C$, $C \to \varepsilon$
$00100$	$S \to AB$, $A \to 0A$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 0C$, $C \to \varepsilon$
$101$	$S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 1C$, $C \to \varepsilon$
$10111$	$S \to AB$, $A \to \varepsilon$, $B \to 1C$, $C \to 0C$, $C \to 1C$, $C \to 1C$, $C \to 1C$, $C \to \varepsilon$
$011$	$S \to AB$, $A \to 0A$, $A \to \varepsilon$, $B \to 1C$, $C \to 1C$, $C \to \varepsilon$