Gramática sensible al contexto para el lenguaje de la copia

Question

Necesito encontrar una gramática sensible al contexto para el lenguaje de la copia %#% $ #%

Esto es lo que tengo hasta ahora:

$\begin{eqnarray} S & \Rightarrow & \lambda \; | \; X \\ X & \Rightarrow & 0XA \; | \; 1XB \\ XB & \Rightarrow & CX \\ XA & \Rightarrow & DX \\ CX & \Rightarrow & X0 \\ DX & \Rightarrow & X1 \\ 0X & \Rightarrow & 0 \\ 1X & \Rightarrow & 1 \end{eqnarray} $

Esto funciona bien para 0101 pero no incluso para 00 o 11.

¿Por favor me podrias ayudar a encontrar una solución?

Gracias de antemano!

Answer 1

Una manera simple de hacer esto es crear primero duplicado de word y, a continuación, ordenar, por ejemplo,

$$\begin{aligned} S &\to D_1D_2T \\ T &\to A_1A_2T \mid B_1B_2T \mid E \\ \alpha_2\beta_1 &\to \beta_1\alpha_2 \\ A_2E &\to E0 \\ B_2E &\to E1 \\ D_2E &\to F \\ A_1F &\to F0 \\ B_1F &\to F1 \\ D_1F &\to \varepsilon \end{aligned}$$ para $\alpha, \beta \in \{A,B,D\}$. Intuitivamente, primero se crea un motor de arranque marca de $D_1$, luego de un final-marca de la primera palabra $D_2$, y luego los pares de cartas hasta el final $E$. La meta-regla ordena todos los $A_1$$A_2$, pero sin intercambiar $A_1$ $B_1$ o $A_2$ $B_2$ (y lo mismo para $B$s y $D$s). El $E$ sello representa el $A_2$ $B_2$ no-terminales y después de alcanzar el medio cambia en el $F$ que representa el $A_1$$B_1$. Finalmente, después de $F$ llega a la mendicidad, desaparece.

Espero que esto te ayuda ;-)

Answer 2

Mi idea sería generar de la siguiente manera:

Primer producir cadenas de la forma $w H \tilde{w}^R E$ donde $\tilde{w}^R$ es que algunos "isomorfo" la versión de la inversa de $w$, consideran que el uso de $A$ en lugar de $0$ $B$ en lugar de $1$, e $E$ es de algún marcador para el final.

El próximo transformar subcadenas de la forma$HA \rightarrow H0$$HB \rightarrow H1$.

El próximo propagar estos terminales a la final, o al menos hasta que están a la izquierda de otro terminal: $0A \rightarrow A0$, $0B \rightarrow B0$, $1A \rightarrow A1$, $1B \rightarrow B1$, y también $0E \rightarrow E0$, $1E \rightarrow E1$.

Finalmente, convertir $HE \rightarrow \lambda$.