Hola, me puse a hacer algunos finales y me tope con esto:

a) indique de que tipo de lenguaje se trata (si es tipo 0,1,2,3)
b)si corresponde diseñar un automata finito que reconozca el lenguaje, de lo contrario diseñar una gramatica que lo genere

y esto es la solucion:
[img] Uploaded with ImageShack.us[/img]

mis preguntas:

en el punto "a" no entiendo como deduce que es de tipo 2, por el libro puedo reconocer que tipo es mirando sus producciones y si me dan algo asi estoy perdido

en el punto "b" es correcto esto?
" se llama lenguaje tipo 3 o regular y un automata finito se construye sobre expreciones regulares o lenguajes regulares y al ser del tipo 2 no es posible construir el automata finito".

Otra pregunta: si tengo una exprecion regular puedo afirmar que es del lenguaje tipo 3?

no entiendo, este autómata no generaría el lenguaje?





edit: me acabo de dar cuenta del error: es imposible hacer que la cantidad de a^n y c^n sean la misma con un autómata, osea es imposible de establecer el valor de n

no entiendo, tu automata me parece que si genera igual cantidad de As y Cs de hecho aa*bc*caaaa* no es una exprecion que genera misma cantidad de As y Cs??

Sí, como dice Vallo, no se puede en un lenguaje regular (tipo 3 creo).

Creo que para esto tenés que usar un autómata de pila o algún otro autómata, pero el lenguaje regular no te lo permite, así que es de otro tipo seguro .

(31-07-2010 17:51)Intips escribió:  no entiendo, tu automata me parece que si genera igual cantidad de As y Cs de hecho aa*bc*caaaa* no es una exprecion que genera misma cantidad de As y Cs??

No
Fijate
aabccccccccccccccaaaa es una expresion valida del automata. Tene en cuenta que el asterisco no representa la misma cantidad para cada vez que aparece. Solo quiere decir 0 mas veces.

Ahii te respondooo, bancame que escriboo

Si a vos te dan una definición de un lenguaje, y ves que los exponentes de las letras tienen alguna relación, por ejemplo:

\[L={a^n b^n / n>0\]
\[L={a^n b^t c^2n / n>=0\], que son lenguajes independientes de contexto.

\[L={a^n b^n c^n / n>0\], que es un lenguaje sensible al contexto.

el lenguaje no puede ser nunca de tipo 3, es decir, un lenguaje regular.

Es por eso que:
- No existe una expresión regular con la cual se lo pueda representar.
- No existe un autómata finito que lo reconozca (sí un autómata con pila o una máquina de Turing, pero eso no se ve).

Es decir que la única manera que tenés de representarlo, digamos, es con una gramática.

En el caso del ejercicio que posteaste, es un lenguaje independiente de contexto, con lo cual lo podés representar con una gramática independiente de contexto. Hay infinitas gramáticas equivalentes que pueden representarlo, ahí te ponen una.

ah cagense todos, ya me gano de mano

(31-07-2010 18:39)guidok escribió:  Si a vos te dan una definición de un lenguaje, y ves que los exponentes de las letras tienen alguna relación, por ejemplo:

\[L={a^n b^n / n>0\]
\[L={a^n b^t c^2n / n>=0\], que son lenguajes independientes de contexto.

\[L={a^n b^n c^n / n>0\], que es un lenguaje sensible al contexto.

Primero. muchas gracias a todos por molestarce
y segundo, en los ejemplos que me pasaste veo que todos tienen exponentes con alguna relacion, todos, y no entiendo como reconocer los "lenguajes independientes de contexto" de un "lenguaje sensible al contexto."

por ejm:
\[L={a^n b^n c^n / n>0\]
\[L={a^n b^n c^n / n>0\]
no se a que lenguajes pertenecen pero pareciera que pertenecen al mismo, sin embargo lo definiste como lenguajes distintos.

gracias

A VER SI ME DEJAN A MIII jaja estoy respondiendo ..!

---

Creo que la pregunta que haces seria mas facil de explicar si supieses lo que es un automata de pila. Como eso no se ve en discreta, nos la arreglamos con lo que sabes..

Un lenguaje Independiente de contexto es generado por gramaticas Independientes de contexto.
Estas tienen la forma A-->(T+x)* es decir, de un NOTERMINAL-->cualquier combinacion de terminales/no terminales

Un lenguaje Sensible de contexto es generado por gramaticas Sensibles al contexto.
Forma A-->T donde A y T son cualquier combinacion de terminales/no terminales. 2 restricciones nomas: A no puede ser "e" (osea el neutro) y ademas el cardinal de A |A| debe ser menor o igual al de B |B|; es decir, cuando apliques las producciones a la derecha debe haber igual o mayor cantidad de "caracteres" que a la izquierda.

Cual es el dilema con esos lenguajes potenciales ? casi nunca son LR, y como no ves automata de Pila lo mas comodo que podes hacer es generarte una gramatica, y mirando la gramatica decidir que tipo de gramatica es ; con eso sabes que lenguaje genera y por consiguiente su tipo.
Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3.
Consejo: Cuando tengas 2 potencias y hay relacion entre estas(osea los exponentes tienen la misma variable "n"), suelen ser LIC o L. sensibles al contexto (LSC).
Si son solo 2 potencias \[ a^n b^n \] y estan "pegadas" son LIC; ahora si tenes 3 o mas potencias, o no estan "pegadas", (por Ejemplo \[a^n b^t c^n\])seran LSC porquee no tenes manera, con una LIC, de generar ese \[b^t\] en el medio.
En cambio, fijate que si fuese por ejemplo \[a^n b^n c^t\] esta la podes generar con una GIC (para los que estuvimos en sintaxis, lo vimos en Automatas de pila, que lo genera). ¿Por que ? Porque es como generar \[a^n b^n\] y a este concatenarle \[c^t\]. Lo mismo para \[c^t a^n b^n\]; NO ASI para \[a^n b^n c^t d^n e^n \]

---

Por que esta ultima no ? Tras hacer el \[a^n b^n \] haces el \[ c^t\] y luego cuando quieras hacer el \[d^n e^n\] no tenes forma de saber cuantas "n-veces" hiciste la primera parte. Con "hacer" me refiero cuantas veces aplicaste esa produccion (que en sintaxis veras que se llama derivar)
Por eso fijate, si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC
(ojo que hablamos de exponentes variables, osea, \[a^n\]; y no de por ejemplo \[a^3\]

(31-07-2010 19:08)gonnza escribió:  Si son solo 2 potencias \[ a^n b^n \] y estan "pegadas" son LIC; ahora si tenes 3 o mas potencias, o no estan "pegadas", (por Ejemplo \[a^n b^t c^n\])seran LSC porquee no tenes manera, con una LIC, de generar ese \[b^t\] en el medio.

Che Gonza pero \[a^n b^t c^n\] es independiente de contexto, no sensible, creo.

Por ejemplo, lo podés generar con esta gramática, que es una GIC:

\[S -> aSc | TT -> bT | b\]
(en este caso con \[n>=0; t>=1\])

La mejor forma de definirlo para mí sería...

- Si hay dos letras que tienen exponentes relacionados, es Independiente. Por ejemplo: \[L={a^n b^t c^n / n>=0;t>=1}\].

- Si hay tres letras que tienen exponentes relacionados, es Sensible. Por ejemplo: \[L={a^n b^n c^m d e^n / n>=1;m>=1}\]

entonces es como yo explique, y eso que dije "excepcion" es en realidad un ejemplo mas jkaja
entre todo se me chispoteo xD

---

la definicion correcta seria algo asi como el mismo exponente aparece HASTA 2 veces, es LIC.

Por ejemplo \[a^n b^n c^t d^t e^x f^x\] es LIC, y aparecen 3 exponentes distintos.. La cosa va en la cantidad de repeticiones de un exponente: Si son mas de 2, tiene que ser LSC, y si son 2 o menos, es LIC

Creo que ahi entre mi amigo guidok y yo te explicamos la duda.. Cualquier cosa, repregunta

Perfecto. muchas gracias gonzza, entendi todo lo que escribiste. solo que habria que aclarar esto:

"Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3".

por que en el libro a un LIC se lo conoce como TIPO 2, que es la respuesta al ejercicio que plantie.

no habia leido los ultimos comentarios.

"si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC" me parece que esto esta mal, veredad? por que en el mismo ejercicio que adjunte hay 2 potencias relacionadas y estan separadas y si es LIC. por lo que en sintecis seria:

"no importa si estan pegadas o no, si hay 2 o menos exponentes relacionadas seran LIC y si hay 3 o mas seran LSC"

es asi?

Cita:Perfecto. muchas gracias gonzza, entendi todo lo que escribiste. solo que habria que aclarar esto:

"Justamente cuando crees una gramatica te dara de la forma de una GIC, es decir que esa GIC genera un LIC, y por lo tanto es Tipo 3".

por que en el libro a un LIC se lo conoce como TIPO 2, que es la respuesta al ejercicio que plantie.

My mistake Fe de erratas :
LR---> TIPO 3
LIC---> TIPO 2
LSC-->TIPO 1
LIrrestricto --> TIPO 0;

Cita:si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC" me parece que esto esta mal, veredad? por que en el mismo ejercicio que adjunte hay 2 potencias relacionadas y estan separadas y si es LIC. por lo que en sintecis seria:

"no importa si estan pegadas o no, si hay 2 o menos exponentes relacionadas seran LIC y si hay 3 o mas seran LSC"

es asi?

Estan separadas por "b"; pero cuando nos referimos con guidok a "separadas" nos referimos a separadas por una cantidad indeterminada de caracteres (osea, que no podes saber cuantos hay en el medio". Es decir, cuanto tenes un \[b^x\] en el medio (osea, otro exponente). Eso quise decir cuando puse

Cita:Por eso fijate, si hay mas de 2 potencias relacionada (un mismo "n"), o si hay 2 y no estan pegadas, es imposible que sean una LIC
(ojo que hablamos de exponentes variables, osea, \[a^n\] ; y no de por ejemplo \[a^3\]

En el caso de tu ejemplo, vos tenes un "b" en el medio, es decir, siempre hay 1 y solo 1 caracter, no tenes que habra "n-caracteres" (osea, no tenes un rango de cantidad de caracteres posible). Por eso la definicion que te dimos seria correcta cuando "pegados" en el sentido de que no estan separados por algun \[a^x\], osea, por algun exponente distinto.
Quizas no se entendio bien, espero que ahora si

Mil gracias che, ahora termino de cerrarme todo. Espero sacarme discreta de ensima, gracias por la ayuda