¿Cómo definir una gramática que crea un lenguaje a partir de palabras de otra gramática sin una de las letras?

Question

Dejemos que $G=(V,T,P,S)$ sea una gramática libre de contexto sin $\epsilon$ reglas. Definir una gramática libre de contexto $G'$ que crea un lenguaje que consiste en todas las palabras de $L(G)$ sin una de las letras de una palabra que pertenece a $L(G)$ . Por ejemplo, si $ab\in L(G)$ entonces $a\in L(G')$ y $b\in L(G')$ .

La solución al problema es la siguiente:

Dejemos que $G'=(V\cup V', T,P',S')$ . $$ \forall (A\to \alpha)\in P\implies (A\to \alpha)\in P'\\ \forall (A\to \alpha B\gamma)\in P, B\in V\implies (A\to \alpha B\gamma)\in P'\\ \forall (A\to \alpha t\gamma)\in P, t\in T\implies (A\to \alpha\gamma)\in P' $$

---

Por qué $\forall (A\to \alpha B\gamma)\in P'$ porque $\alpha, \gamma$ son cadenas de símbolos de la pila (no sólo letras), por lo que no pueden dividirse (como por ejemplo, $\forall (A\to \alpha B\gamma)\in P, B\in V\implies (A\to \alpha)\in P'\quad\land\quad (A\to \gamma)\in P'$ )?

Answer 1

En tu solución te faltaron algunos primos esenciales.

La idea es que la nueva gramática es igual que la original, salvo que pierde uno de los símbolos generados. Pero debe quedar claro que hay exactamente un terminal que desaparece. El símbolo primado tiene la "tarea" de (no) generar ese terminal que desaparece. Le pasa esta tarea a uno de sus sucesores.

Axioma $S'$ , al igual que $S$ pero recuerda que hay que eliminar un símbolo en la derivación que sigue.

Si $A\to \alpha\in P$ entonces $A\to \alpha\in P'$ (Los símbolos no cebados se comportan como antes).

Si $A\to \alpha B\gamma\in P$ entonces $A'\to \alpha B' \gamma\in P'$ (La tarea se delega en un sucesor)

Si $A\to \alpha t\gamma\in P$ ( $t$ terminal) entonces $A'\to \alpha \gamma\in P'$ (no hay más primos, el terminal fue eliminado)

Answer 2

Gracias por el post, atascado con el mismo problema. Yos, creo que en tu pregunta te lías con la gramática y la representación de autómatas pushdown (que tiene pila). En este caso, creo que en la solución que has publicado, α,γ∈ $\bigl((V∪V′)∪T\bigr)^\ast$ . Me gustaría que alguien lo aprobara.
En cuanto a mí, a partir de la notación dada, todavía no está claro cuándo se produce la transmisión de las variables V a V'.