Cómo crear una gramática para el complemento de $a^nb^n$ ?

Question

Tengo una L de lengua: $$ \Sigma = \{a,b\} , L = \{a^nb^n | n \ge 0 \} $$

Y estoy intentando crear una gramática libre de contexto para co-L .

He creado la gramática de L:

P = {
  S -> aSb
  S -> ab | epsilon
}

En co-L, no sé cómo asegurar, que no habrá el mismo número de a,b . ¿Debería crear algo así?

P = {
  S -> aSb
  S -> a | b | aS | bS
}

Answer 1

Consideremos esta lógica: una frase en el complemento de $L$ debe comenzar con $b$ o terminan en $a$ o si empieza por $a$ y termina con $b$ la subcadena entre las dos no debe estar en $L$ (debe estar en el complemento de $L$ ). Así que podemos escribir:

$S\to bA|Aa|aSb$

$A \to aA|bA|\epsilon$

Answer 2

Podemos descomponer este lenguaje en la unión de varios lenguajes más sencillos:

L = { $a^i b^j$ | i > j } { $a^i b^j$ | i < j } $(a b)^b(a b)^a(a b)^$ .

Es decir, todas las cadenas de a's seguidas de b's en las que el número de a's y b's difiere, unidas con todas las cadenas que no sean de la forma $ a^ib^j$ .

En primer lugar, podemos conseguir la unión de los CFG de las tres lenguas:

S $S_1|S_2|S_3$

Ahora, el conjunto de cadenas { $a^ib^j$ | i > j } es generado por un CFG simple:

$S_1 aS_1b|aS_1|a$

Del mismo modo para { $a^ib^j$ | i < j }:

$S_2 aS_2b|S_2b|b$

Por fin, $(a b)^b(a b)^a(a b)^$ se genera fácilmente de la siguiente manera:

S3 XbXaX

X aX|bX|

---

Fuente: http://cseweb.ucsd.edu/classes/su99/cse105/sample2.pdf

Answer 3

Las cadenas no de forma $a^nb^n$ vienen en varios grupos.

Una cadena que empiece por $b$ puede obtenerse a través de $S \to bS_1$ entonces $S_1 \to aS_1|bS_1|\varepsilon $

Una cadena puede tener un número positivo de $a$ entonces un número positivo de $b$ entonces un número positivo de $a$ y luego cualquier cosa. Este lleva más pasos: $S\to aS_2$ entonces $S_2 \to aS_2|bS_3$ entonces $S_3 \to bS_3|aS_4$ entonces $S_4 \to aS_4|bS_4|\varepsilon.$

Las cadenas restantes del complemento tienen $a$ seguido de $b$ sino más bien $a$ a la izquierda o más $b$ a la derecha. Para más información $a$ a la izquierda, utilice $S \to aS_5,$ entonces $S_5 \to aS_5|aS_5b|\varepsilon$ Por último, para más $b$ sobre el uso correcto $S \to S_6b,$ y luego $S_6 \to S_6b|aS_6b|\varepsilon.$

No soy un experto en este tema, pero lo anterior me parece intuitivamente que cubre todas las cadenas en el complemento de $a^nb^n$ sin dejar que se produzca ninguno de estos últimos.

Answer 4

A^n b^n significa igual número de a que sigue a igual número de b

Gramática g={N,T,P,S}

N- No Terminales-{A}

T- Terminales-{a,b,epsilon}

p- Producción

S->A

A->aAb

A->Epsilon(^)

S- Símbolo de inicio-{S}

Espero que esta respuesta sea correcta ANWAR MULLA (AGCE)