PUERTA | PUERTA-CS-2006 | Pregunta 84

Which one of the following grammars generates the language L = {aibj | i ≠ j}

El lenguaje L contiene las strings: { abb, aab, abbb, aabbb, aaabb, aa, bb, ……. }, es decir, en una string, y Entonces i ≠ j.

Aquí las Gramáticas A, B y C también generan la string “ab”, donde i = j, y muchas más strings con i = j, por lo tanto estas gramáticas no generan el lenguaje L, porque para una string que pertenece al lenguaje L, el exponente i no debería ser igual al exponente j.

Gramática D : esta gramática nunca genera una string con el mismo número de a y b, es decir, i=j. Por lo tanto, esta gramática genera el lenguaje L. Por lo tanto, la opción D.