Examen febrero 2018

Examen febrero 2018

de Matilde Ines Gomez De Salazar Gigirey -
Número de respuestas: 1

pARA ESTA GRAMATICA:

Sea L1 = { a^P b^ q c^r      / (p+r) mod 2 = q mod 3 , q>=1}

La solucion la plantearon :

S → bB | aA 

B → bB1 | cC1

 B1 → bB2 | bbB

 B2 → bB | cC2

 C1 → cc | ccC1 

C2 → c | ccC2

 A → bA1

 A1 → bA2 | cC2

 A2 → bA3

 A3 → cC1


Pero de este modo por ejemplo la tira  aaab que es una  tira del lenguaje(ya que aaa es 1 mod 2 y b 1 mod 3 ) y en el autómata que pusieron en la solucion también puede crearse pero con las reglas me parece que no se puede crear, o me esta faltando ver algo que no me  doy cuenta .Saludos.

En respuesta a Matilde Ines Gomez De Salazar Gigirey

Re: Examen febrero 2018

de Diego Garat -

hola:

la solución, efectivamente, está mal, porque solo se puede generar una letra a, cuando evidentemente las tiras podrían tener más, como bien señalás.

las gramáticas lineales salen muy fáciles con el AF correspondiente, y en este caso parecería que la variable S corresponde a q0, y la variable A a q1. luego, estaría faltando la producción equivalente a g(q1,a)=q0, o sea:

A -> a S

lo mismo sucedería con A3 y la transición g(q9,b)=q7

A3->bA1

además, no están bien contemplados los casos finales. por ejemplo, faltarían A-> b y A3->b, por ser nulable A1 (final q7)


saludos,

d.-