Gramáticas Incontextuales

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)

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

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.