6. Considere el lenguaje L = {aⁿb^n+mc^m}

a) Proponga una GLC que genere L

b) Elimine de la gramatica las producciones vacias y las inútiles, si las hay

c) Pruebe por inducción que la gramatica es correcta

d) Obtenga el AP correspondiente

a) Gramatica Libre del Contexto

S AC

A aAB

A ab

B b

C BCc

C bc

b) NO hay producciones inutiles

c) Prueba inductiva

Paso Base

En 1 paso

S AC abbc

A ab

C bc

Hipotesis:

S ^k αAβC

Paso de Induccion:

S ^k αAβC 1) αAβC

A aAB

C BCc

B b

Ultimo Paso

S ^k-1 αAβC ^k αaABBCc

^k αaabbbbcc

^k αabβbc

d) Automata de Pila

((p, ε, ε))(q,S))

((p, ε, A))(q,aAB))

((p, ε, A))(q,ab))

((p, ε, B))(q,b))

((p, ε, C))(q,BCc))

((p, ε, C))(q,bc))

((p, a, a))(q, ε))

((p, b, b))(q, ε))

((p, c, c))(q, ε))