Gramáticas Incontextuales

#2 Lo que dice el título, gramática incontextual...

primero demuestrale que en un espacio euclideo a b y c conmutan entre si, y una vez echo eso, continua para un solo ejemplo...
lo primero como mero formalismo, pero a esta gente raruna de matematicas les suele molar eso

A ver, el lenguaje generado obviamente es: palabra vacia, a, b, c, aa, ab, ac, ...

Para definir la gramática necesitas las reglas generativas, tomando como símbolo no finales las mayúsculas, siendo la S el inicial, y símbolos finales a, b, c y entendiendo E como la palabra vacía definimos las reglas.

Como es una gramática independiente de contexto podemos incluir reglas que no sean simplemente lineales a derechas o iquizerdas.

Empezamos con el símbolo inicial:
S ::= E | Sc

con esto ya tenemos un número infinito de c's y la palabra vacía, al estar en orden añadimos una regla que nos de otro símbolo intermedio

S ::= c | Sc | B

Seguimos definiendo las reglas que generan bes

B ::= b | Bb | A

A ::= a | Aa | E

Más o menos asi sería, fijate que esté bien formada y GL

(El resto de la tupla la compones tú, so vago)

#5 ¿Qué cojones dices? xDD

Yo no sé de esto (aún), pero #7 diría que ab no es una palabra del conjunto que ha definido #1 ya que tiene igual número de aes que de ces, no? (lo digo porque a lo mejor se haría de manera distinta y me parece curioso el tema, no es por tocar las narices XD)

#7 Sí si la teoría yo también la sé, pero no se puede formar como dices, como ha dicho #9 las palabras a, b o c, no pertenecen a ese lenguaje.
He puesto los casos bases en #1.

#8 Creo que sí, que llevas razón, que no existe una GI para definir {aⁿ bⁿ cⁿ | n>=0}.

#10 Que no melón, que abc no puede ser una palabra del lenguaje que queda (ni a, ni b, ni c, el primer caso base es aab)

Ojo, la que decimos que no es formal es:
{aⁿ bⁿ cⁿ | n>=0}

No el resultado: abc* \ {aⁿ bⁿ cⁿ | n>=0}

Que eso es lo que piden hacer con una GI, pero bueno, en el caso de que no lo fuera, ¿cómo cojones demuestro que no es una GI? xD

Edit: ok, hago lema de bombeo, isi & fast (hacer el AFD es un suicidio).

A ver, IMHO tienes un cacao fino (entre otras cosas porque no se porqué utilizáis terminología tan rara).

Para que quede claro, me refiero a http://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky

Supongo que por gramáticas incontextuales te refieres a gramáticas independientes de contexto o de tipo 2 que incluyen las regulares (aceptadas por autómatas finitos) y las independientes de contexto (aceptadas por autómatas de pila).

Lo más fácil es que pruebes a hacer un autómata de pila, si no puedes hacer un autómata de pila seguramente no sea independiente de contexto y quizás no sea ni formal.

Edit: #13 por lema de bombeo para las independientes de contexto es un coñazo fino, para las regulares es u xⁱ v pero para las independientes si no me equivoco es a bⁱ c d^j e

No estoy seguro porque estoy intentando olvidar todo esto a base de alcohol, pero creo que era asi...

#16 Ese es el lema de bombeo de los regulares, no de todos los independientes de contexto. Es decir, puede que haya uno que sea independiente de contexto pero no regular y no cumpla ese lema de bombeo.

Si quieres te busco el de los independientes de contexto y te lo pongo entero.

PD: Y vaya temario de mierda, sinceramente xD Yo no veo el sentido a estudiar gramáticas y lenguajes sin estudiar autómatas, ya que los autómatas son la herramienta para saber si se aceptan las palabras del lenguaje.

Es como si te enseñan a escribir pero no a usar un bolígrafo xD

PD2: Nosotros los abreviamos llamandolos G0, G1, G2, G3....

Venga, que lo he buscado (C&P a mano de mis apuntes € = pertenece y E = palabra vacía)

Si L es un lenguaje independiente de contexto con infinitas cadenas -> cualquier cadena w€L de longitud mayor que un cierto k€N puede descomponerse como w=uvxyz (siendo u, v, x, y, z € del cierre del alfabeto) de forma que:

u vⁱ x yⁱ z € L para todo i€N

con |vy| >= 1 y con |vxy| <= k

Ej.:

Sea L={0ⁿ 1^n, n€N}

cualquier palabra |w|>= 2 es:

w=uvxyz= 0^n-1 0 E 1 1^n-1

de modo que: 0^n-1 0 E 1ⁱ 1^n-1 pertenece a L para todo i perteneciente a N

|vy| = 2 >=1

|vxy| = 2 <= k

CUMPLE EL LEMA

#18 Pues a mi me parecen mucho más guays e incluso fáciles las máquinas de Turing que los AP xDDD

Y las RNA me ponen palotísimo si no fuera porque sigo sin entenderlas del todo y eso que hace ya unos meses que aprobé aquello xDD

Pero según recuerdo el lema de bombeo se puede utilizar para probar que una gramática NO es regular o NO es independiente de contexto. El que una gramática cumpla el lema de bombeo no implica que pertenezca a esa clase (es condición necesaria pero no suficiente).Sacado de la wikipedia:

"If a language does not satisfy the condition given by the pumping lemma, we have established that it is not context-free. On the other hand, there are languages that are not context-free, but still satisfy the condition given by the pumping lemma."

Este ejemplo me suena bastante de cuando yo estudié estas mierdas (Teoría de automátas y lenguajes formales ftw) y yo diría que no es una GIC.No se me ocurre cómo puedes construir un automáta a pila para reconocerla pero no parece difícil hacer una máquina de Turing para ello (es un lenguaje formal seguro diría yo).

Una pregunta de n00b... Todo esto de las gramáticas viene de los teoremas de incompletitud de Gödel? Me suena que mi padre me dijo algo así pero no estoy seguro. Si es así me alegro porque la optativa de matemáticas que cogeré trata precisamente de estos teoremas.

#23 esta de gramáticas y tal es más rollo de hacer problemas, donde vi lo de Gödel era un puraco infumable de teoria, horrible vaya, pero si estás en mates lo mismo te mola.

Si te piden demostrar informalmente, con comrpobar q genera palabras del lenguaje y q rechaza las palabras q no son del lenguaje te sobra. Vi a echarle un ojo a ver si me acuerdo de algo.

Eso de q el tamaño de las palabras es múltiplo de 3 es falso, porque pejemplo "aaab" y "aaaab" pertenecen al lenguaje. Lo he pensado un poco y lo único q se me ocurre es descomponer la gramática en 6 casos independientes (los q pones en #1) y q la primera regla sea del rollo
S --> S' | S'' | S''' | S'''' | S''''' | S''''''

Yo me pediría una tutoría entre varios y q os lo haga en el despacho xd

#25 Tienes razón, se me ha ido la pinza, pff, mañana le echaré un vistazo a todo.

Dios vuestra asignatura de teoría de autómatas es super chunga XDDDD.

Yo recuerdo q en la mía no había exámenes y había q entregar solo unos ejercicios sencillitos cada 2 semanas.

Vamos, q no se ni de q estais hablando xDDDDDD.