¿Cuál es la CFG de la lengua que genera todas las cadenas sobre el alfabeto $\{a, b, c\}$?

Question

La más obvia que he encontrado, $$S \rightarrow SSS | A | B | C$$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$

Sin embargo, me doy cuenta de que esta CFG es ambious porque podemos generar diferentes de análisis de los árboles de la misma cadena debido a la regla de $S \rightarrow SSS$.
Así que he revisado mi lengua para evitar la ambigüedad de la siguiente manera:

$$S \rightarrow SABC | ASBC | ABSC | ABCS $$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$

donde $S$ es el punto de partida de la variable en ambas gramáticas.

Me pregunto si esta CFG es la correcta? Lo que no estaba seguro de que es la primera regla de $S$, parece un poco redundante, pero no sé cómo solucionarlo de modo que puede generar todas las cadenas sobre el alfabeto $\Sigma = \{a, b, c\}$. Alguna idea?

Actualización
La pregunta es motivado por este problema:

Demostrar que el complemento de la lengua $L = \{a^nb^mc^k, k = n + m\}$ es independiente del contexto.

Puesto que ya he encontrado el CFG para el idioma $L_1 = \{a^nb^mc^k, k \neq n + m\}$, lo que estoy tratando de hacer es encontrar la CFG para su complemento, que incluye dos partes:

1. $L_1$
2. $L_2$ = Cualquier cadena de más de alfabeto $\Sigma = \{a, b, c\}$ que no está en el formulario de $a^mb^nc^k$.

Así que si no puedo encontrar el CFG para 2, la unión de estas dos lenguas es también CFG añadiendo un extra de regla: $$S \rightarrow S_1 | S_2$$ donde $S_1$ es a partir de la variable de $L_1$, e $S_2$ es a partir de la variable para $L_2$.

Answer 1

Por qué no utilizar el siguiente sencillo de la gramática, donde S es el punto de partida de la variable?

S $\rightarrow$ BS | $\varepsilon$

B $\rightarrow$ a | b | c

Editar para su actualización:

Quieres demostrar que $L_2$ es de contexto libre.
Sin embargo, como dijo Yuval $L_3 = \{a^mb^nc^k \mid m,n,k \in \mathbb{N}\}$ es regular.
Ahora, desde la $\Sigma^*$ es regular y $\Sigma^*$\ $L_3$ es tu idioma deseado, sabemos que $L_2$ es regular ya que regular idiomas están cerradas en virtud de diferencia, lo que implica que $L_2$ contexto libre.

Answer 2

Para el principal problema,

Demostrar que el complemento de la lengua $L = \{a^nb^mc^k, k = n + m\}$ es independiente del contexto.

Una cadena es en el complemento de L si y sólo si contiene (al menos) uno de $ba$, $ca$ o $cb$ como una cadena, o una letra distinta de $a,b$ o $c$ en el caso de un mayor alfabeto. Esto se expresa fácilmente como una unión de varios idiomas, o como un autómata que recorre la cadena en busca de alguno de los prohibidos subcadenas.

Answer 3

La respuesta por @zyx va un largo camino, pero si la cadena está en$a^* b^* c^*$, usted tiene que asegurarse de que la condición en el número de símbolos es violado. Esta condición puede salir mal, porque (1) no hay demasiadas $c$, o (2) hay muy pocos. Escrita en términos de una gramática, con $L$ menos $a$$b$$c$, e $G$ para más: $$ \begin{align*} S &\rightarrow L \mid G \\ L &\rightarrow A c \\ A &\rightarrow A c \mid B \\ B &\rightarrow a B c \mid C \\ C &\rightarrow b C c \mid \epsilon \\ G &\rightarrow a D \mid E \\ D &\rightarrow a D \mid B \\ E &\rightarrow a E c \mid b F \\ F &\rightarrow b F \mid C \end{align*} $$ Las lenguas mencionadas por zyx son regulares, por lo que el contexto libre, y los lenguajes libres de contexto son cerrados respecto a la unión.

Otra es obtener el idioma $\{ a^n b^m c^k \mid n + m \ne k \}$ por las operaciones que preservar el contexto libertad. Primero considere el $L_1 = \{0^n 1^m \mid n \ne m \}$, generado por: $$ \begin{align*} S &\rightarrow 0 A \mid B 1 \\ A &\rightarrow 0 A \mid E \\ B &\rightarrow B 1 \mid E \\ E &\rightarrow 0 E 1 \mid \epsilon \end{align*} $$ El $A$ rama asegura demasiados 0, $B$ rama demasiadas 1; $E$ da tantos 0 como 1, y es el contexto libre por el cierre de propiedades.

Toma ahora la homomorphism definido por $h(a) = h(b) = 0$, $h(c) = 1$. A continuación, $h^{-1}(L_1) \cap a^* b^* c^*$ es el idioma que estamos buscando.