Gramaticas

GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO

1) Mediante la siguiente gramática libre de contexto, derivar la cadena aa³b.

S→aE
E→A
E→B
A→b
A→Aa
B→b | bB

S aE A Aa Aa Aa b2-3) Con la siguiente gramática libre de contexto derivar la cadena zazabzbz por la derecha y por la izquierda.
S → zMNz
M → aMa
M → z
N → bNb
N → z

Derivación por laizquierda:
S zMNz zaMaNz zazaNz zazabNbz zazabzbz

Derivación por la derecha:
S zMNz zMbNbz zMbzbz zaMabzbz zazabzbzArboles de Derivación
1) Sea la GIC
S → AB
A → aA | a
B → bB | b
la cadena w = aabbb puede ser derivada

S

A Ba A b B

a b Bb
2) De la siguiente gramática obtener la cadena aabbba

S ASB | 
A aAb | 
B bBa | ba
S

A S Ba A b b a

a A b3) Sea la gramática

S SbS | ScS | a

Obtener la cadena abaca S

S c SS b S a

a a
Formas Normales de Chomsky1) Sea la gramática incontextual G definida por las siguientes reglas:

S → bA | aB
A → bAA | aS | a
B → aBB | bS | b


Gramática “pseudo-Chomsky”

S → CbA |...