Buenas tardes, si me pudieran dar una mano con este ejercicio se los agradeceria mucho. Estoy preparando el parcial de discreta y rindo en dos dias. Saludos!

Yo estoy en las mismas. Tiene gramatica tipo 2, por lo tanto no es posible obtener automata finito

Como llegaste a la conclusión de que tiene una gramatica del tipo 2 ? eso es lo que no me termina de quedar claro tampoco...

Tipo 2 y 3 ambos tienen en lado izquierdo un no terminal, en el derecho es donde se diferencian, hasta donde se es que en el dalo derecho tiene que terminar con un Vt (terminal).

Vn---->Vn.Vt l Vt (ese seria un tipo 3)

Vn ---->Vt.Vn (ese seria un tipo 2)

Es hasta donde yo se, seguramente es asi porque yo lo hice en el parcial creyendo que era un tipo 3 y hice el automata. pero me la dieron como equivocada porque era del tipo2 . Si hubiera tenido claro ese concepto hubiera aprobado

es tipo 2 porque hay dos no terminales en el lado derecho, con tipo 3 solo puede haber un solo Vn

el lenguaje generado es: (ab)*acc*ba

yo hice el automata y me saque 10, asi q se podia hacer

(09-12-2013 12:05)rihardmarius escribió:  es tipo 2 porque hay dos no terminales en el lado derecho, con tipo 3 solo puede haber un solo Vn

el lenguaje generado es: (ab)*acc*ba

yo hice el automata y me saque 10, asi q se podia hacer

tengo entendido que solo se puede hacer un automata finito de una gramatica tipo 3. En este caso es tipo 2. si se puede hacer un automata pero no seria finito, seria automata pila (que no se ve en discreta).


YO HICE EL AUTOMATA TAL COMO LO HICISTE

Si yo tenia en entendido eso tambien. Que el automata finito se podia hacer con una gramatica del tipo 3 nada mas... Gracias por la respuesta !

entonces hice un automata de pila

como la gramatica es tipo 2, el lenguaje es tipo 2

La gramática es de tipo 2 pero existe una gramática equivalente de tipo 3, equivalente significa que generan el mismo lenguaje. Básicamente te das cuenta al sacar la expresión regular del lenguaje, se puede ver como puso rihardmarius que existe expresión regular, no todos los lenguajes tienen. Un ejemplo es el lenguaje a^n º b^n, no existe expresión regular porque no hay forma de asegurar usando solo los * que las dos letras se repitan la misma cantidad de veces.
Todo lenguaje que pueda ser expresado por una expresión regular es un lenguaje regular, o sea de tipo 3, o sea generado por una gramática tipo 3, por eso se puede hacer el autómata, y es finito, el de pila es otra cosa que ni vimos.

Saludos!

Osea que un lenguaje tipo 3 es generado por una gramática del tipo 3 y también por gramáticas que pueden ser equivalentes (como en este caso que la gramática es del tipo 2) ?

tiene razon nuestro amigo m685

pasa q las de tipo 3 estan incluidas en las de tipo 2, (y tipo 2 en tipo 1 y asi) por eso siempre se puede sacar una gramatica tipo 2 a partir de una de tipo 3

en este caso se dio la casualidad de que inferimos una de tipo 3 a partir de una de tipo 2, q loco no?

No es que lo dijiste alrevez, no se puede sacar una gramatica de tipo 2 a partir de una gramatica de tipo 3, porque la 3 esta incluida en la 2. Por eso en el ejercicio se podia sacar una gramatica de tipo 3 a partir de una de tipo 2

Podría decirse que todas las gramáticas son tipo 1, pero para clasificarlas se toma el grupo menos abarcativo al que pertenece. Tipo 1 no te dan nunca, o son tipo 2 o tipo 3. Si son tipo 2 no se puede obtener el autómata finito, saaaalvo que tenga una gramática equivalente tipo 3, como en este ejercicio, que no fue casualidad, el año pasado hicieron lo mismo, la trampa es a conciencia y caen muchos porque no suelen hacer esta aclaración.

En definitiva para clasificar la gramática lo único que te fijas es que todas las producciones sean de la forma: No terminal -> terminal, o No terminal -> terminal º No terminal ( º es la concatenación), si encontrás alguna producción que no respete eso automáticamente es tipo 2; en el ejercicio la única producción que correspondería a una gramática tipo 3 es la de Y -> cY/c

Para saber si podés hacer el autómata finito simplemente sacás la expresión regular (o si no te sale el lenguaje y te fijas si lo podés expresar con alguna expresión regular). Si encontrás la ER es de tipo 3 y podés hacer el autómata, caso contrario decís que la gramática es de tipo dos y genera un lenguaje no regular entonces no es posible hacer el autómata (muy difícil que suceda, la idea es evaluar como hacés el autómata xD).

Me quedo (ab)*ac*cba
osea
cuando "despejo" Y, hago Y = c*c, luego concatenandolo con lo anterior queda
(ab)*ac*cZ

y el lenguaje me quedo asi:

L(G1) = { a^n, b^m , c^m , \[n\geq 2\], \[m\geq 1\]}

La expresión regular no te la pide, igual está bien lo que hiciste, si te fijas más arriba ya estaba resuelta, lo único que sería cc* y no c*c, o sea (ab)*acc*ba, la primera c representaría que al menos debe aparecer una vez, y la otra con el * que se puede repetir indefinidas veces.

Ahora el lenguaje está mal, tiene que ser igual que la expresión regular pero con variables en vez de los *, sería L(G1) = { (a b)^m a c^n b a/ m>=0 ^ n>0}, m puede ser igual que 0 porque no necesariamente tiene que comenzar en ab, podría comenzar con una a, en cambio en el caso de la c en vez de escribirla dos veces como en la expresión regular (cc*) se la escribe una sola vez pero se la eleva a una potencia mayor que 0, por lo tanto el primer valor de n sería 1, por lo que sí o sí deberá aparecer una vez.