[Febrero 2017 - Ejercicio 2] - Como llegan a la Gramatica de L3?

[Febrero 2017 - Ejercicio 2] - Como llegan a la Gramatica de L3?

de Francisco Fernandez Cecchetto -
Número de respuestas: 2

Estimados,

En este ejercicio se pide dar una gramatica para el lenguaje

gramatica

en las soluciones se llega a las siguientes producciones:

gramatica

Estoy intentando entender como se llega a estas producciones y cual es la relación que tienen que hace que cumplan con las condiciones del lenguaje pero no logro darme cuenta ni del razonamiento que lleva a esta solución ni por que es la solución correcta.

Desde ya agradezco cualquier explicación que me ayude a entenderlo

PD: las demás gramáticas si las entendí pero esta me resulta muy difícil de interpretar.

En respuesta a Francisco Fernandez Cecchetto

Re: [Febrero 2017 - Ejercicio 2] - Como llegan a la Gramatica de L3?

de Diego Garat -

hola:

las gramáticas regulares son más fáciles de pensar como en la transformación de autómatas: cada variable es un estado, y las producciones son las transiciones que te permiten pasar de un estado al otro (ejercicio 7 del práctico 5).

en este caso, por ejemplo:

  • S representa cantidad par de aes, bes y 0 ces.   (par, par, 0)
  • A representa cantidad impar de aes, par de bes y 0 ces  (impar, par, 0)
  • A1 impar de aes, par de bes y >0 de ces  (impar, par, >0)

luego:

  • si en S viene una a voy de (par, par, 0) a A(impar, par, 0) 
  • si en A viene una a voy de (impar, par, 0)  a S (par, par, 0) 
  • si en A viene una c, en cambio, voy de (impar, par, 0) a  A1 (impar, par, >0)   .
  • si en A1 viene una c, voy de (impar, par, >0)  a A1 (impar, par, >0)  

en otras palabras, S, A, B y D son las combinaciones de paridades de aes y bes cuando no se procesaron ces, mientras que C, A1, B1 y D1 replican la lógica  pero cuando al menos se procesó una ce.

saludos,

d.-