PARTE COMÚN:
- Construir una gramática lineal por la derecha que genera todas las cadenas w (es decir, w Є{0,1,2}*) que son divisibles sin resto por 4 (se interpreta w como base 3).
PREGUNTAS DE TEORÍA:
- Sea L un lenguaje regular, ¿existe una gramatica lineal por la derecha G que genere L, tal que L(G)=L cuyo numero de variables es igual a RL+5?
- Si una ER contiene el * (de kleene), ¿es infinito?
- Si un automata determinista minimo completo, tiene un estado no-final (a parte de los estados finales), ¿entonces el no-final tiene arista reflexiva si lo dibujamos?
- Si un AFPND acepta con pila vacía, ¿existe un AFPND que acepta en estado final?
- Dada una GLI ambigua G, ¿es posible construir una GLD no ambigua que genera el mismo lenguaje L(G’)=L?
PARTE PRÁCTICA (Sólo para los que no sigan los criterios de evaluación contínua):
- Construye una gramatica en forma normal de Chomsky que genere:
L={a^ i b^j c^k d^l | (i=j y k=l) o (i=l y j=k); i,j,k,l >=0}
Ejemplos: aabbcccddd,abcd,aaabbccddd,aaaabbbb… - Transforma esta GLD en GLI:
G=({$,A,B,C},{a,b,c},{$->aA|bB, A->a$|cC|a, B->bB|c, C->cC|c$|b},$)
Mis agradecimientos a Ales, ya que sin ella esta entrada no hubiese sido posible 😀
