En este grupo En todos

Foro de Matemáticas



Gramatica numeros romanos

Jessy_fuensa
Escrito por Jessy_fuensa
el 30/04/2009

Hola, necesito construir una gramática independiente del contexto que describa el lenguaje formado por los números romanos. Ya no se que hacer... Mil gracias

Escrito por Mathspf
el 02/05/2009

Estimada amiga: dejame ver si entendi... Lo que tu quieres es contruir un automata finito deterministico ( o nodeterministico) que te permita describir el lenguaje formado por los numeros romanos? Es decir que con este automata puedas representar a todos los numeros romanos y solo a estos?

Jessy_fuensa
Escrito por Jessy_fuensa
el 02/05/2009
Hola, primero gracias por contestar... Estoy estudiando psicología y en una asignatura llamada psicologia del pensamiento, nos han pedido construir "La gramática de los número romanos". He presentado dos propuesteas pero las dos propuestas estaban mal. Te voy a poner cada propuesta con su contestación del profesor.
Primera propuesta:

1º Si a la derecha de una cifra romana se escribe otra igual o menor, el valor de esta se suma a la anterior.

2º La cifra I colocada delante de la V o la X les resta una unidad, la X precediendo a la L o la C les resta diez unidades y la C delante de la D o la M les resta cien unidades.

3º En ningún número se puede poner una misma letra mas de tres veces seguidas.

4º Las letras V, L, y la D no pueden duplicarse porque otras letras (X, C, M) representan su valor duplicado.

5º Si entre dos cifras cualesquiera existe otra menor, esta restara su valor a la siguiente.

No se puede anteponer una I, a una C. La única letra que se puede anteponer a la C, es una X. Al igual que a V, sólo se puede anteponer I, y a L, sólo se antepone X, a D y M, sólo se antepone C.

6º El valor de los números romanos queda multiplicado por mil tantas veces como rayas horizontales se coloquen encima de los mismos.

S:= A|B|E|F|G|H|J||K|P|O

A:= i|ii|iii
B:= v|iv|vA|A
E:= xB|B|x|ix
F:= ix

G:= xxE|xE|E|xxxix
H:= l|lG|xl|xlB|xlF|G

J:= xc|xcB|xcF|H

K:= c|cJ|cc|ccJ|ccc|cccJ| λ

P:= cd|cdJ|d|dK|K

O:= m|mO|mP|cm|cmJ

Contestación:

Aunque la gramática propuesta está todavía lejos de la solución, aporta ideas interresantes, más que en la gramática misma, en las "reglas" o explicaciones que preceden. Naturalmente el problema es traladar estas reglas de formación a producciones. Esa es la tarea a realizar. La gramática permite derivar directamente expresiones compuestas, como p. Ej. Ii, iii, etc. Esto no está permitido. Las expresiones deben derivarse composicionalmente y es obvio que iii es la composición sobre i. Seguís pensando en términos de una gramática libre de contexto; deberías de pensar en cómo representar el contexto. Y estas son mis observaciones para seguiros animando. Un afectuoso saludo,

Segunda propuesta:

La forma de abordar el problema consiste en suponer que todos los números se construyen como un número decimal, es decir, que un número tendrá unidades, decenas, centenas, etc.

En primer lugar diseñaremos una gramática independiente del contexto, para que resulte más fácil y e intuitivo llevar a cabo la construcción de la misma. Posteriormente la transformaremos en gramática regular.

<NÚMEROSROMANOS> := <MILES><CENTENAS><DECENAS><UNIDADES> | <CENTENAS><DECENAS><UNIDADES>|<DECENAS><UNIDADES>|<UNIDADES>

<MILES> := m | mm | mmm

<CENTENAS> := c | cc | ccc | cd | d | dc | dcc | dccc | cm | λ

<DECENAS> := x | xx | xxx | xl | l | lx |lxx |lxxx | xc | λ

<UNIDADES> := i | ii | iii | iv | v | vi | vii | viii | ix | λ

Como podemos apreciar en esta gramática, se pueden representar números hasta 3999, ya que sino necesitaríamos nuevos símbolos.

Una vez construida la gramática independiente del contexto vamos a transforma en una gramática regular. Se propone la separación entre los números que contengan unidades de millar, centenas, decenas y unidades, con el fin de modularizar el diseño. La gramática queda del siguiente modo.

<NÚMEROSROMANOS> := <MILES> | <CENTENAS> | <DECENAS> | <UNIDADES>

<MILES> := m <CENTENAS>|mm <CENTENAS>|mmm<CENTENAS> | <CENTENAS>

<CENTENAS> := c <DECENAS>|cc<DECENAS>|ccc<DECENAS>|cd<DECENAS>|d<DECENAS> |dc<DECENAS>|dcc<DECENAS>|dccc<DECENAS>|cm<DECENAS> | <DECENAS>

<DECENAS> := x<UNIDADES> |xx<UNIDADES> |xxx<UNIDADES> |xl<UNIDADES> | l<UNIDADES> |lx<UNIDADES>|lxx<UNIDADES>|lxxx<UNIDADES>|xc<UNIDADES> | <UNIDADES>

<UNIDADES> := i | ii | iii | iv | v | vi | vii | viii | ix | λ

Contestación:La gramática que me adjuntáis no es correcta. La gramática de los números romanos carece de unidades, decenas y centenas. Es una aproximación incorrecta, porque X es una decena pero se escribe un único carácter, y IV es unidad y se escribe con dos caracteres. Además, las reglas de producción que proponeis permite la derivación directa de expresiones que deben derivarse por composición, no directamente como proponeis.
No hay ninguna razón especial para usar un tipo de gramática u otra. Es un problema de conveniencia y de dar cuenta de las expresiones que se quieren explicar. Simplemente, ocurre que en los números romanos juega un importante papel, pero nada obliga a proponer una gramática u otra. En todo caso a lo que obliga una gramática de los números romanos es a producir números romanos de manera inambigua, y no producir nada que no sea romano. Un afectuoso saludo,


Muchisimas graciassss



Escrito por Mathspf
el 04/05/2009

Hola:

Que te parece esta propuesta...

I*= i ,ii, iii

Unidades*=i*,iv,v,vi*,ix (unidades)

X*=x,xx,xxx

Decenas*= & , x*,xl,l,lx*. Xc (decenas) (aqui & representa vacio)

C*=c,cc,ccc

Centenas*=&,c*,cd,d,dc*,cm

Millares*=&,m,mm,mmm

Asi
todo numero romano se presenta como

S= <millares*><centenas*><decenas*><unidades*> , /s en este caso la diagonal representa la multiplicacion por mil...

Espero sea lo que necesites de cualquier modo si tuviesen alguna duda o no fue lo que requieres me gustaria que me comentaras...

Jessy_fuensa
Escrito por Jessy_fuensa
el 04/05/2009
Hola!

Gracias por molestarte.
Para mi está perfecta, pero ya madé una separando en unidades, decenas, centenas.... Y ya has visto lo q me contestó el profesor, q los numeros romanos carecen de unidades, decenas....
No tengo ni idea de como hacerlo.
La única posta q dio en clase es q debe ser una gramitica cuyas reglas de producción produzcan unicamente numeros romanos y no otra cosa.......

Aparte de esto. Tenemos un programa q simula una maquina de turing y tenemos programarla para q sume numeros binarios. Tampoco sé como hacerlo. Si es que estudio psicología, como lo voy a saber......
Agradeceria tu ayuda
Gracias

Escrito por Mathspf
el 04/05/2009

Estimada amiga:

Ya probaste la gramatica que te mande... Segun yo.. Genera todos los numeros romanos que quieras.. Y ademas no genera otra cosa... Porque no intentas probar generando numero a ver si encuentras uno que no se pueda.. Intenta probar contra ejemplos... Busca algun defecto... Pero segun veo... La sugerencia de tu profesor era generarlo asi.. A partir de unidades decenas centenas y millares... Y fue asi como lo genere yo... No le hice tantas pruebas pero no veo ambiguedad, ni que falten elementos... En realidad no puedo dedicarle mucho tiempo porque ando con otras cosas.. Pero si estoy interesado en este problema...

Si entiendes la forma en que trabaja la gramatica... Ademas segun recuerdo es valido usar el vacio... Porque al final se tratar de generar un conjunto de palabras a partir

De un conjunto de reglas... Que deben ser unicas, no ambiguas, etc.. Etc...

Repecto al otro problema que es exactamente lo que tiene que hacer la dichosa maquina de nuestro querido amigo... Turing?

Jessy_fuensa
Escrito por Jessy_fuensa
el 04/05/2009

Mil gracias.
Se la he mandado y estoy esperando contestación.
Lo de la maquina de turing tengo q programarla para que sume números binarios. Q agobio!
Graciassssss de nuevo

Escrito por Mathspf
el 04/05/2009

Hola jessy:

Estuve revisando tus correos... Creo que llama ambiguedad a hecho de que una variable genere varios elementos como u = i ,ii, iii, quisiera que se generaran a traves de produccciones... Lo que no me parece muy grave porque por ejemplo

En lugar de poner u=i ,ii,iii podria ser:

U= ai,i

A=bi,i

B=i

Con esto tendrias i ,ii o iii...

Lo cual no parece que sea tan bueno... Y solo haria un poco mas enredado el asunto...

Y en que lenguaje estan programando?

Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009

Hola!
El profesor no me ha contestado todavia... En cuanto me conteste te lo pongo. Creo q sí, que lo que quiere es algo como lo que me has puesto en el último correo... Si me dice que está mal lo que mandé, pues lo intentamos con lo último que me propones que creo q se acerca más a lo que él quiere
En cuanto a lo de la máquina de Turing. Me aparecen unos dibujos que serán para dibujar el grafo y una cinta infinita debajo que será para programarlo...
Graciass

Escrito por Mathspf
el 05/05/2009

Entonces quieres "programar" de manera teorica el algoritmo de la suma en binario.....


Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009

De manera teorica y practica también... Tengo q dibujar el grafo y programar la cinta para q sume numeros binarios.......

Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009
"entonces quieres "programar" de manera teorica el algoritmo de la suma en binario.....


"

por Mathspf (Mayo 2009)

En cuanto a la gramatica, lo último q me pusiste está bien.... Es como él lo quiere... ¿Como sería?
u= ai,i
a=bi,i
b=i

graciasss



Escrito por Mathspf
el 05/05/2009

Hola:

Pues para no hacerlo mas complicado yo haria algo asi.... En lugar de usar abc como en el ejemplo anterior usaria sub indices i1 i2, x1,x2, c1, c2 etc...

I*= i ,i^1i

I^1=i,i^2i

I^2=i

Donde aparezca la i sola lo cambiaria por i^2

Unidades*=i*,i^2v,v,vi*,i^2x^2 (unidades)
x*=x,x^1x

X^1=x, x^2x

X^2=x

Decenas*= & , x*,x^2l,l,lx*. X^2c^2 (decenas) (aqui & representa vacio)
c*=c,c^1c

C^1=c, c^2c

C^2=c

Centenas*=&,c*,c^2d,d,dc*,c^2m^2
millares*=&,m, m^1m

M^1=m. M^2m

M^2=m

Asi
todo numero romano se presenta como
s= <millares*><centenas*><decenas*><unidades*> , /s en este caso la diagonal representa la multiplicacion por mil...

Capichi?


espero sea lo que necesites de cualquier modo si tuviesen alguna duda o no fue lo que requieres me gustaria que me comentaras...

Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009

Hola, gracias por todo lo que estas haciendo. Aqui tienes la contestación que me a dado el profesor.
lamento deciros que tampoco esta propuesta es satisfactoria. No se trata de introducir símbolos ad hoc ni interpretaciones originales de cómo proceder. Como podéis comprobar por sí mismas ni esta propuesta ni la anterior tiene el formato exigido para una gramática de los números romanos, donde se identifican símbolos terminales y no terminales y reglas de producción. No quiere decir esto que no podáis emplear potencias pero ocurre que la potencia es una operación, NO define una regla de producción, y tampoco está correctamente usada; nunca podría ocurrir que i elevado a 2 diera lugar a i. De otra parte, tendríamos expresiones compuestas que deberían obtener por composición y no directamente como también ocurría en la propuesta anterior. Tal vez es más útil, habida cuenta de los retos que tenemos pendientes centrarse en los siguientes retos, como la máquina sumadora de Turing, o el próximo sobre Redes Neurales, el último de curso. No conviene empecinarse y hacerlo desviándose cada vez más del propósito original. Un muy afectuoso saludo,

Escrito por Mathspf
el 05/05/2009

Hola: oye... Tendras ejemplos gramaticas que haya generado en clase... Porque no me queda claro lo de las reglas de produccion y como las usa... La verdad no te miento... Esto lo lleve hace como 6 años y ya estoy algo empolvado... Pero tal vez observando sus ejemplos pueda recordar como se hace en fin... Aqui andamos...

Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009

Ejemplos en clase no hemos visto ninguno, de todas formas te escribo lo que hemos dado va?
Weno tengo un ejemplo hecho pero no se si tiene mucho que ver:

(Sumatorio), es q no se como poner el simbolo asiq te lo pongo con una S vale?

ST (Simbolos terminales)= (0, 1,... 9)
SN (Simbolos no terminales)= (N, C)
A (Axioma)= N
P (Producciones)= N:=NC
N:= C
C:= 0
C:=...9

Siendo N:= NC/C
C:= 0/ /9


Y puso un ejemplo para que vieramos que está bien hecha, el ejemplo fue el siiguiente:

¿Es 345 un número entero?
N=NC=NCC=CCC=3CC=34C=345 N (en 7 pasos)=345


Esto es lo único que tengo

Escrito por Mathspf
el 05/05/2009

Esta muy bien....

Si estoy viendo los ejemplos y estaba leyendo un poco... Y ya se porque esta mal el asunto.... Es que una gramatica libre de contexto tiene ciertas propiedades que no habia considerado... Y por lo visto debes definirlo asi...

Se debe indicar el alfabeto que en nuestro caso son i v x c d m

Se deben indicar las varibales que es lo que todavia faltan... Por detallar.. Pero esto cumple propiedades tales que como que el alfabeto intersectado con las variables debe ser vacio... Y cosas asi.. Dejame darme un tiempo... Porque estoy en el trabajo.. Pero en cuanto pueda le doy una leida a unos articulos igual y me acuerdo mas y volvemos a intentarlo... Espero que no estes muy presionada con los tiempos...

Espero tener una nueva propuesta pronto... Cualqueir cosa aqui ando...

Jessy_fuensa
Escrito por Jessy_fuensa
el 05/05/2009

Muchas gracias de nuevo por molestarte.... No, de tiempo vamos bien, tengo q entregar la maquina de turing que estoy trabajando en ella haber que saco... Y esto de la gramatica, pero tendre dos semanas aproximadamente....
Gracias y graciasss

Escrito por Mathspf
el 06/05/2009

Hola otra vez yo... Es que ya me obsesione con esto.... Porque me molesta no recordar ciertas cosas... En fin...

Estuve revisando alguno articulos... Y un libro y formalmente no dice que la expresion

A= i | ii | iii no pueda ser usada... De hecho

Aqui te envio un texto (de los 5 que ya consulte) y hasta donde entiendo no indica lo contrario... Me gustaria que le preguntaras a tu profesor como define una gramatica libre de contexto... Porque de acuerdo a la definicion del libro lo anterior es valido... O mas aun que te diga porque la produccion

A= i | ii | iii no puede ser usada... Si cumple la condicion de variable igual a cadena de terminales y variables.... Ademas es bantante util porque sirve para representar un numero muy pequeño de posibilidades...

Por que si define a=i b=a | aa | aaa me parece casi absurdo...

Segun entiendo la unica condicion sobre las producciones es que tengan una variable igual a una combinacion de terminales o variables.... Y eso se cumple en lo anterior...

Ademas revisando la respuesta que te dio anteriormente... No esta entendiendo mi notacion donde pongo i^2 me refiero a la variables i2 "lease i sub 2" y no a la operacion i al cuadrado... Es que en este editor es complicado escribir subindices...

Seria bueno ver que diche de la propuesta anterior hechas estas aclaraciones...

En fin... Sigo con esto y espero tus comentarios...

Jessy_fuensa
Escrito por Jessy_fuensa
el 06/05/2009

Buenos días!
Le pregunté lo que me dijiste y esta ha sido su contestación:
En la primera gramática q me mandaste existía algo muy interesante, me refiero a las reglas de formación de los números romanos, donde me ponías bien explicadas todas las reglas de formación de los números romanos, el problema es traladar estas reglas de formación a producciones. Esa es la tarea a realizar. La primera gramática que me enviaste es la que más se acerca pero permite derivar directamente expresiones compuestas, como p. Ej. Ii, iii, etc. Esto no está permitido. Las expresiones deben derivarse composicionalmente y es obvio que iii es la composición sobre i. Seguís pensando en términos de una gramática libre de contexto; deberías de pensar en cómo representar el contexto.

Esta ha sido la contestación, te adjunto aqui la primera gramatica que le envié...

Para hacer la gramática con números romanos, hemos tenido en cuenta las reglas de construcción de los números romanos:

1º Si a la derecha de una cifra romana se escribe otra igual o menor, el valor de esta se suma a la anterior.

2º La cifra I colocada delante de la V o la X les resta una unidad, la X precediendo a la L o la C les resta diez unidades y la C delante de la D o la M les resta cien unidades.

3º En ningún número se puede poner una misma letra mas de tres veces seguidas.

4º Las letras V, L, y la D no pueden duplicarse porque otras letras (X, C, M) representan su valor duplicado.

5º Si entre dos cifras cualesquiera existe otra menor, esta restara su valor a la siguiente.

No se puede anteponer una I, a una C. La única letra que se puede anteponer a la C, es una X. Al igual que a V, sólo se puede anteponer I, y a L, sólo se antepone X, a D y M, sólo se antepone C.

6º El valor de los números romanos queda multiplicado por mil tantas veces como rayas horizontales se coloquen encima de los mismos.

GRAMÁTICA NÚMEROS ROMANOS:

S:= A|B|E|F|G|H|J||K|P|O

A:= i|ii|iii
B:= v|iv|vA|A
E:= xB|B|x|ix
F:= ix

G:= xxE|xE|E|xxxix
H:= l|lG|xl|xlB|xlF|G

J:= xc|xcB|xcF|H

K:= c|cJ|cc|ccJ|ccc|cccJ| λ

P:= cd|cdJ|d|dK|K

O:= m|mO|mP|cm|cmJ

Creo que es la gramática que aun estando lejos de la solución él considera que aporta cosas importantes......
Un saludo