TeoComp B2011: Problema 5,1,1

Diseñar gramáticas independientes de contexto para los siguientes lenguajes:

a) El conjunto {0^n1^n | n >= 1 }, es decir, el conjunto de todas las cadenas de uno o más ceros seguidos por un número igual de unos.

Para ese lenguaje es suficiente con:

S --> 0S1 | 01

b)  El conjunto { a^ib^jc^k | i =/= j o j =/= k }, es decir, el conjunto de cadenas de a seguida de cadenas de b seguidas por cadenas de c, tales que hay o bien un número distinto de a y b, o bien un número distinto de b y c, o ambas cosas.

S --> AB | CD
A -->  aA | lambda
B --> bBc | E | cD
C --> aCb | E | aA
D --> cD | lambda
E --> bE | b

"Para entender como trabaja esta gramática, considere lo siguiente:

A genera cero o más a's.
D genera cero o más c's.
E genera una o más b's.
B primero genera un número igual de b's y c's, entonces o bien produce una o más b's, via E, o uno más c's, vía cD. Es decir, B genera las cadenas in b^*c^* con desigual número de b's y c's.
En forma similar, C genera un número desigual de a's y b's.
Así, AB genera las cadenas en a^*b^*c^* con números desiguales de de b's y c's. Mientras que CD genera las cadenas con números desiguales de a's y b's. "

Traducido desde http://infolab.stanford.edu/~ullman/ialcsols/sol5.html

Considere ahora estas implementaciones de solucionadores en Prolog:

Para a)

Usando DCGs:

p([Der|Rest]) --> cero, p(Rest), uno.
cero --> [0].
uno --> [1].

En Prolog simple:

p(de(S,N), S, R) :- cero(S, R1), p(N, R1, R2), uno(R2, R).

Los argumentos nos permitirían registrar las derivaciones!. (de(S,N): de S obtengo N usando esta regla!).

Para b) (no lo he probado!).

p --> no_ab, C.
p --> A, no_bc.
no_ab --> a(I), b(J), { not(I=J) }.
no_bc --> b(J), c(K), { not(J=K) }.

a(0) --> [a].
a(I) --> a(J), { I is J + 1 }.

Falta definir a b y a c. Se animan!.