3.9 LENGUAJES NO REGULARES

El lema de bombeo para lenguajes no regulares

Gracias a este lema podremos demostrar que ciertos lenguajes infinitos no son regulares. Es importante hacer notar que el lema de bombeo es una herramienta adecuada para demostrar que un lenguaje no es regular, pero no lo será para demostrar que un lenguaje si es regular (por el hecho de que existen algunos lenguajes no regulares que la cumplen). Por tanto, si un lenguaje no cumple el lema de bombeo no es regular, pero si lo cumple no podremos decir si es o no regular.

Enunciado del Lema de Bombeo

Para todo lenguaje regular infinito L, existe una constante n, dependiente de ese lenguaje, de forma que si w es una cadena de L con ¦w¦ ≥ n, podemos partir w en tres cadenas, x, y, z, de forma que:

• w = xyz,

• y ≠ ε (o dicho de otro modo, que ¦y¦ ≥ 1),

• ¦xy¦<= n

• Para cualquier k ≥ 0, la cadena xy^kz pertenece a L.

Más formalmente:

∀ lenguaje regular infinito L sobre un alfabeto Σ

∃ n ∈ N /

∀ w ∈ L / ¦w¦ ≥ n

∃ x, y ,z ∈ Σ* / w = xyz, y ≠ ε, ¦xy¦<= n,

∀ k ≥ 0, xy^kz ∈ L

Demostración de que un lenguaje no es regular

Dado que para todo lenguaje regular infinito se cumple el lema de bombeo, si nos dan un lenguaje infinito y demostramos que para él no se cumple, habremos demostrado que no es un lenguaje regular. Como el lema de bombeo es una propiedad que se cumple para todas las cadenas de longitud mayor o igual a cierta n, bastará encontrar una cadena de ese lenguaje, de longitud mayor o igual a esa n, que no se pueda “bombear” para demostrar que el lenguaje no es regular. Con esta idea en mente, los pasos a dar para demostrar que un lenguaje dado no es regular son los siguientes:

1. Elegir una palabra w que pertenezca al lenguaje dado. Podemos elegir cualquier palabra del lenguaje, pero debe ser una cuya longitud sea mayor o igual que una constante n que desconocemos (la constante del lema de bombeo). Como desconocemos n, lo habitual será elegir una palabra en función de un n cualquiera y cuya longitud sea mayor o igual que n.

2. El lema de bombeo dice que si el lenguaje fuera regular, podríamos encontrar una forma de partir esa palabra w en tres, cumpliendo ciertas restricciones, y que esa partición sería bombeable. Como queremos demostrar que el lenguaje no es regular, tendremos que demostrar que no hay ninguna forma de partir la palabra en tres cumpliendo las restricciones del lema, y que después se pueda bombear siempre.

3. Finalmente bastará con encontrar una constante k ≥ 0 que haga que ninguna de las particiones posibles de w sea bombeable.

Más formalmente, para demostrar que un lenguaje L sobre un alfabeto Σ no es regular habrá que demostrar que:

∀ n ∈ N

∃ w ∈ L / ¦w¦ ≥ n,

∀ x, y ,z ∈ Σ* / w = xyz, y ≠ ε, ¦xy¦<= n,

∃ k ≥ 0 / xy^kz ∉ L

Ejemplo de demostración de que un lenguaje no es regular

Sea el lenguaje L={a²ⁿbⁿn≥0}. Demostrando que L no es regular

1. Comprobamos si L es regular por medio del lema de bombeo.

Suponemos que L es regular. Entonces existe una constante n tal que ∀ w ∈ L, ¦w¦ ≥ n,

w = xyz, y ≠ ε, ¦xy¦ <= n, teniendo que xyⁱz ∈ L.

Se elige w = a²ⁿbⁿ, w ∈ L y ¦w¦= 3n y por tanto ¦w¦≥ n.

2. Probamos, por ejemplo, con la siguiente descomposición

w=xyz

- x = a

- y = a

- z = a²^n-2bⁿ

3. Bombeamos:

xy²z = a a a a^2n-2bⁿ = a²ⁿ⁺¹bⁿ

Podemos observar que xy²z no pertenece a L. Por lo tanto, el lenguaje es no regular.

INTEGRANTES:


*TORRES HERNANDEZ JONATHAN DE JESUS
*REYES SANTIAGO SEVERIANO
*RAMIREZ GARCIA PABLO ALBERTO

Nota:

Información recopilada de la siguiente liga:

http://www.alumnos.inf.utfsm.cl/~dcontard/ili-255/documents/ull/uz_cps_lema_bombeo_regulares.pdf

AUTOMATA PUSH-DOWN

Un autómata de pila o Push-Down es un autómata que cuenta con un mecanismo que permita almacenamiento ilimitado y opera como una pila. El autómata de pila (se abrevia PDA de sus siglas en inglés Push-Down Autómata) tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto. El símbolo que se encuentra más a la izquierda se considera como que está en la “cima”. El dispositivo será no determinístico y tendrá un número finito de alternativas de movimiento en cada situación como se muestra en la siguiente figura un autómata de pila.Los movimientos serán de dos tipos. En el primer tipo de movimiento se utiliza un símbolo de entrada. Dependiendo del símbolo de entrada, del símbolo de la cima y el estado de control finito, es posible un número de alternativas. Cada alternativa consiste en un estado posterior para el control finito y una cadena (posiblemente vacía) de símbolos, para sustituir al símbolo que se encuentra en la cima de la pila. Después de seleccionar una alternativa, la cabeza de entrada avanza un símbolo como se ilustra en la siguiente figura: La figura anterior muestra el avance de un símbolo de entrada (q1, c, B), a un estado posterior y sustitución de la cima de la pila {(q2, B)}.

El segundo tipo de movimiento conocido como movimiento ε es parecido al primero, excepto que el símbolo de entrada no se utiliza y la cabeza de la entrada no avanza después del movimiento. Este tipo de movimiento permite al PDA manipular la pila sin leer símbolos de entrada como se muestra en la figura:Manipulación de la pila sin leer símbolo de entrada. Existen dos modos de aceptar un lenguaje por un autómata de apilamiento. El primero consiste en definir el lenguaje aceptado como el conjunto de todas las entradas para las cuales una sucesión de movimientos ocasiona que el autómata de pila vacíe su pila.
La segunda manera es designando algunos estados como estados finales y definimos el lenguaje aceptado como el conjunto de todas las entradas para las cuales alguna selección de movimiento ocasiona que el autómata de pila accede un estado final.

Consideremos el siguiente ejemplo de autómata de pila definido por:

Obsérvese que no hay transiciones para todas las ternas posibles de estado, símbolo de entrada y símbolo de pila. Por lo tanto, si el PDA pasa a un estado para el cual no se especifica un estado siguiente y una acción de la pila para los símbolos actuales de la pila y la entrada, el PDA no puede volver a realizar ningún movimiento.
En particular, cuando el autómata está en el estado q4, que es el estado de aceptación, no hay ninguna transición sea cual sea el símbolo de la cima y de la entrada. Si el PDA se mueve al estado q2, entonces obsérvese que cada vez que a aparece en la entrada se apila una B en la pila.
El PDA permanece en el estado q2 hasta que se encuentra la primera b y entonces se mueve al estado q3, ninguna b puede preceder a una a.
Finalmente, en el estado q3 sólo se consideran las b’s y, cuando se encuentra cualquier b, se desapila B de la pila. (Sólo pueden desapilarse las B’s que fueron apiladas, debido a encontrarse una a en la entrada). Las únicas cadenas que acepta el PDA pertenecen al lenguaje puesto que son las únicas cadenas de entrada que, una vez que han sido consumidas, causan que el PDA termine en el estado final q4.

CARACTERÍSTICAS DEL APD:
*Cinta de entrada de sólo lectura.
*Pila, acepta lectura y escritura (pop y push).
*Cabeza lectora, se mueve a derecha (movimiento implícito).

MOVIMIENTOS QUE UN APD PUEDE REALIZAR.
Movimiento Dependiente de la entrada
Tiene en cuenta el símbolo corriente en la cinta de entrada. Luego, una transición de este tipo tendría la siguiente forma:

MOVIMIENTO INDEPENDIENTE DE LA ENTRADA
No se tiene en cuenta el símbolo corriente en la entrada. Interpretación: igual a la anterior, excepto que no miramos el símbolo de la entrada para tomar una decisión.
¿Qué pasa cuando γ = λ? - En este caso se reemplaza el tope de la pila por la cadena de longitud nula, es decir se realiza la operación pop sobre la pila. Esto vale para cualquier tipo de movimiento.

EJEMPLO:

FUENTES DE INFORMACIÓN:
http://www.monografias.com/trabajos16/automatas-y-gramaticas/automatas-y-gramaticas.shtml#automatasdepila
http://es.scribd.com/doc/52381938/push-down

REALIZADO POR LAS ALUMNAS:
SANTIAGO CRUZ ROSA ELVIA
CARLOS DE LA CRUZ LORENA LIZETH
MENDOZA HERNÁNDEZ DAYSI

ELIMINACION DE FACTORES COMUNES IZQUIERDOS

ELIMINACION DE FACTORES COMUNES IZQUIERDOS UN AUTOMATA FINITO O MAQUINA DE ESTADO FINITO ES UN MODELO MATEMATICO DE UN SISTEMA QUE RECIBE UNA CADENA CONSTITUIDA POR SIMBOLOS DE UN ALFABETO Y DETERMINA SI ESA CADENA PERTENECE AL LENGUAJE QUE EL AUTAMATA RECONOCE. DEFINICION FORMAL FORMALMENTE, UN AUTOATA FINITO (AF) PUEDE SER DESCRITO COMO UNA 5-TUPLA (S,W,T,S,A) DONDE: W ES UN ALFABETO; S UN CONJUNTO DE ESTADOS; T ES LA FUNCION DE TRANSICION: ; ES EL ESTADO INICIAL; ES UN CONJUNTO DE ESTADOS DE ACEPTACION O FINALES. EJEMPLO 1 W= {0,1}, S = {S1, S2}, T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})} S = S1 A = {S1}. } FORMAS DE REPRESENTAR UN AUTOMATA FINITO ADEMAS DE NOTAR UN AF A TRAVES DE SU DEFINICION FORMAL ES POSIBLE REPRESENTARLO A TRAVES DE OTRAS NOTACIONES QUE RESULTAN MAS COMODAS. FACTORIZACION DE TERMINOS COMUNES IZQUIERDOS INMEDIATOS. EXISTEN GRAMÁTICAS QUE TIENE PRODUCCIONES DE LA FORMA A ¡ Å ß1 Å ß2 COMO POR EJEMPLO: S ¡ I E T S E S I E T S DONDE Å ES EL TÉRMINO COMÚN EN LAS PRODUCCIONES DE A. SIN EMBARGO PARA PODER LLEVAR A CABO EL ANÁLISIS SINTÁCTICO DE LAS MISMAS MEDIANTE ALGUNAS TÉCNICAS SE DEBE ELIMINAR LOS TÉRMINOS COMUNES IZQUIERDOS LLEVANDO A CABO EL PROCESO DE FACTORIZACIÓN SIGUIENTE: LAS PRODUCCIONES A ¡ Å ß1 Å ß2 SE TRANSFORMAN EN LAS SIGUIENTES A ¡ Å A´ A´¡ ß ß2 LAS CUALES NOS GENERAN EL MISMO LENGUAJE. EXISTE UN NUEVO SÍMBOLO NO TERMINAL A´ EN LA GRAMÁTICA, EL CUAL NO ALTERA LA GRAMÁTICA DEL LENGUAJE. GENERALIZANDO EL PROCEDIMIENTO PARA N PRODUCCIONES DE A QUE TIENEN FACTOR COMÚN IZQUIERDO: 1. AGRUPAR TODAS LAS PRODUCCIONES DE A, SIN IMPORTAR CUANTAS SEAN. A ¡ Å ß1 Å ß2 ... Å ßN Λ *DONDE Λ REPRESENTA OTRAS PRODUCCIONES DE A QUE NO TIENEN FACTOR COMÚN IZQUIERDO . 2. REMPLAZAR LAS PRODUCCIONES DE A A UN CONJUNTO EQUIVALENTE MEDIANTE LA SIGUIENTE TRANSFORMACIÓN A ¡ Å A´ Λ A´¡ ß1 ß2 ... ßN

Decidibilidad y Lenguajes Decidibles (Por Juan de Dios Aguilar Martínez)

A manera de introdución les recomiendo leer el dócumento de Daniel Padilla Ezquivel decibilidad, poniendo especial atención a el aporte que nos dá el tema 5.1 mismo que hace referencia a el tema de nuestro plan de estudios.

Ir al documento de Padilla Ezquivel

Ahora suponiendo que ya se sobreentienden un gran número de los conceptos que se tratarán y que la mente de nosotros ya está avierta a una buena interpretación... A continuación... les precento el desarrollo de nuestro tema....


INTRODUCCIÓN:

Como parte de la Carrera de Ingeniería en Sistemas Computacionales, estudiamos lo que es Decibilidad ya que se utiliza en la Teoría de Autómatas y Lenguajes Formales, todo esto dentro de lo que llamamos Teoría de la Computación. Por ello desarrollaremos este ensayo como una opción para que otros estudiantes puedan tener información de este tema.

Vamos a Definir que es la Decibilidad, sus áreas y formas de aplicación, para poder darnos una mejor idea de su utilidad. (Falta definir mejor).

Aunque para poder entender este tipo de textos se deben de tener ciertos conocimientos previos, como saber que es y cómo funciona una Maquina de Turing, y también conocimientos propios del lenguaje técnico de Teoría de la Computación.

DESARROLLO:

En este Ensayo citaremos algunas definiciones de Decibilidad para una mayor comprensión de este texto:

•“En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas. Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema”

•“Se dice que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es”.

•“DECIDIBLE: adj. Log .Mat .Dícese de las proposiciones de un sistema axiomático cuya verdad o falsedad puede demostrarse dentro del sistema”.

Según las Definiciones Anteriores, podemos llegar a concluir que se tiene Decibilidad si podemos encontrar una fórmula, método o algoritmo que nos permita decidir si cierta cadena pertenece a una estructura.

Como ya se había mencionado, la Decibilidad nos sirve en los lenguajes Formales, por lo tanto veremos cuáles son los Lenguajes y su Clasificación:

“Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llama lenguajes recursivos”.

TIPOS LENGUAJES


En vista de que uno de los objetivos de este ensayo es hacer más digerible para el lector este tema, primero daremos una definición general acerca de los lenguajes formales y después una definición más técnica para una mayor comprensión:

“Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que, por ejemplo La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.

Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:

•las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.

•Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.

•Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más cortó entre esos dos vértices.

•Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se para en un tiempo finito al procesar esa entrada.

Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.”

Aquí presentamos una definición más formal:
“Sea M un autómata de Turing: ¿w ∈ L (M)?

Posibles respuestas:
1.M termina en un estado final ⇒ w ∈ L (M)
2.M termina en un estado no final ⇒ w∉L(M)
3.M no termina ⇒ w ∉L (M)

Es un lenguaje RECURSIVO si existe un autómata de TuringM que para ante cualquier entrada y tal que:
•Si w ∈ L ⇒ M termina en un estado final
•Si w∉L ⇒ M termina en un estado no final

L es un LENGUAJE RECURSIVAMENTE NUMERABLE
Si existe un autómata de TuringM tal que:
•Si w ∈ L ⇒ M termina en un estado final
•Si w∉L ⇒ M termina en un estado no final o M no termina”.


“Así, en una primera aproximación, los problemas pueden clasificarse en:
•Computables (o decidibles)
•No computables (o no decidibles)”


Un algoritmo indecidible:
Sea el siguiente algoritmo, debido a Lagarias (1985) :
Por ejemplo, si el valor inicial de X es 7, va tomando los valores:
7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

1 Entrar X
2 Mientras X≠1 hacer:
3 Si X es par, X = X/2
4 Si no, X = 3X +1
5 Parar

Sin embargo, no se puede demostrar que este algoritmo llegue siempre a pararse,
para cualquier número positivo de entrada. Aunque tampoco puede demostrarse lo contrario: que exista algún número para el cual el algoritmo no se para nunca.

El problema de la parada:

Dado un programa (o algoritmo) A y un valor de la entrada X, ¿podemos saber siempre si A se parará o no?
El problema de la parada es no decidible : no hay manera de decir, en general y en un tiempo finito si la ejecución de un programa dado, con una entrada dada, terminará o no.

Además a manera de repaso incluyo 2 videos muy interesantes que encontré que explican de manera adecuada el tema... y algunois de los puntos bases del mismo:

 Decibilidad de teorias lógicas by Oskar21

FUENTES BIBLIOGRÁFICAS:
http://entucaramcfly.blogspot.com/2009/06/teoria-de-la-computacion-primera.html
http://grupodecidibilidad.blogspot.com/2007/08/resumen-ejecutivo.html
http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema3.pdf
http://ji.ehu.es/ALF/MHermo/pdfs/los_m%C3%ADos/Tema4.pdf
http://ji.ehu.es/ALF/MHermo/pdfs/los_m%C3%ADos/Tema4.pdf
http://avellano.fis.usal.es/~lalonso/CTS/computacion.pdf
http://es.wikipedia.org/wiki/Decibilidad
http://www.mitecnologico.com/Main/Decibilidad
Diccionario Enciclopédico Quillet. Tomo IV. Página 231.

ELIMINACION DE RECURSIVIDAD IZQUIERDA

Una gramática es recursiva por la izquierda si tiene un no terminal A tal que existe una derivación A => Aα  para alguna cadena  α. Los métodos de análisis sintáctico descendente no pueden manejar gramáticas  recursivas por la izquierda, así que se necesita una transformación que elimine la recursión por la izquierda.

Recursión por la izquierda inmediata simple  (Eliminación de la recursividad izquierda de las producciones)

En este caso la recursión por la izquierda se presenta solo en las reglas gramaticales

A → A α | β

Donde α y β son cadenas de terminales y no terminales y  β no comienza en A. Esta regla genera todas las cadenas de la forma β, β α, β α α…Todas las cadenas comienzan con una β, seguida por     (0 o mas α). Esta regla gramatical es equivalente a la expresión regular β αⁿ

Para eliminar  la recursión por la izquierda  volvemos a escribir estas reglas gramaticales divididas en dos: una para que primero genere β y otra que genere  las repeticiones de α utilizando recursión por la derecha en vez de recursión por la izquierda:

A → β A´

A´→ α A´|є

Ejemplo Considere de nueva cuenta la regla recursiva izquierda de la gramática de expresión simple:

exp → exp opsuma term | term

La forma de esta regla es  A → A α | β, con A= exp,  α=opsuma term y β=term. Al volverla a escribir para eliminar la recursividad por la izquierda obtenemos que

exp → term exp´

exp´→ opsuma term exp´ |є

Recursión por la izquierda inmediata general  (Eliminando la recursión directa por la izquierda de una producción general)

Este es el caso en que tenemos producciones de la forma

A → A α₁| A α₂|……|A α n | β₁ | β ₂|……… | βm

Donde ninguna β₁…… βm comienzan con una A. Después se sustituyen las producciones de A por:

A→ β₁ A´| β ₂ A´|…….| βm  A´

A´→ α₁ A´| α₂ A´|…….| α n A´|є

Ejemplo. Considere la regla gramatical

exp → exp + term | exp -  term | term

Eliminemos la recursión por la izquierda de la manera siguiente

exp → term exp´

exp → + term exp´ | - term exp´ |є

Recursión por la izquierda general (Eliminación de la recursividad izquierda de una gramática completa puede ser mas difícil debido a la recursividad izquierda indirecta).

Es indirectamente recursiva porque elimina por completo la recursividad izquierda

El algoritmo que aquí describimos  eliminara sistemáticamente la recursión por la izquierda general de una gramática. Siempre funciona si la gramática no tiene ciclos (donde un ciclo es una derivación de por lo menos un paso que comienza y finaliza con el mismo no terminal: A => A) o producciones  є (producciones de la forma A → є)

Algoritmo

Entrada La gramática G sin ciclos ni producciones є

Salida Una gramática equivalente sin recursión por la izquierda

1.- Ordénense los no terminales en un orden A₁, A₂,……..,An

2.- PARA i =: 1 hasta n HACER

       COMIENZA {PARA i}

      PARA  j=: 1 hasta i-1 HACER

Reemplace cada producción de la forma  Ai → Ajβ por las producciones:

Ai → α₁β| α₂β|……| αk β

Donde:

Aj→ α₁| α₂|……| αk

Son todas las producciones de Aj actuales

Eliminar  la recursividad inmediata por la izquierda entre las producciones de Ai

Ejemplo: Dada la gramática

S→ Aa | b

A→ Ac|Sd|є

Se ordenan los no terminales S, A. No hay recursión directa por la izquierda entre las producciones de S, de modo que no ocurre  nada durante el paso 2 para el caso i=1. Para i=2, se sustituyen las producciones de S en A→ Sd para obtener las siguientes producciones de A.

A → Ac|Aad | bd  |є

Eliminando la recursión directa por la izquierda entre las producciones de A, se obtiene la siguiente gramática

S → Aa | b

A→bdA´ | A´

A´→c A´|ad A´| є

La eliminación de la recursión por la izquierda no cambia el lenguaje que se esta reconociendo, pero modifica la gramática y, en consecuencia, también los arboles de derivación.

Bibliografía : 

• Compiladores. Principios Técnicas Y Herramientas.- .Aho.Sethi.Ullman
• Construcción de compiladores principios y practica - Kenneth-C-Louden-International-Thomson-Editores

Integrantes de Exposición: 

• Imelda Montiel Santos 
• Yuliana Areli Garcia Domingez
• Pedro Eduardo Cortez Mayorga

Innovaciòn Educativa

Innovación Educativa.

La innovación educativa es la introducción de cambios o novedades en la práctica educativa, es un cambio en las actitudes, en el comportamiento, en los procedimientos de la institución, en los contenidos, los métodos, etc., esto es con la finalidad de mejorar las actividades que el docente desempeña y obtener mejores resultados, aumentar la calidad educativa y el mejoramiento del aprendizaje de los estudiantes. Esta tiene carácter intencional, ya que desde su planeación se deben establecer los objetivos deseados  y su éxito es medido en base a las metas alcanzadas. Además puede ser aplicada en la educación presencial, en la educación a Distancia y en la educación Mixta.

El docente como uno de los actores principales en la innovación educativa debe estar consciente que esta no es  fácil ya que nos enfrentamos a factores que se oponen como compañeros que no pretenden cambiar y a estudiantes con apatía, pero perseverar nos traerá al final buenos resultados. Al introducir cambios en la educación se debe considerar que se requiere de esfuerzo y se tendrá una repercusión tanto en el docente como en el alumno, se requiere aumentar recursos útiles para el aprendizaje, y se requiere de atención al alumno cuando este lo necesita.

De lo anterior podemos decir que la aplicación de la innovación educativa traerá impacto en cada uno de los agentes que en esta intervienen,  en la institución educativa ya que esta tendrá que invertir en infraestructura para mejorar la calidad de la educación; en los docentes ya que tendrán que organizar, planificar, impartir,  tutorizar, motivar, etc.;  y en los alumnos ya que deben adquirir nuevos conocimientos, habilidades y capacidades

Es importante que cuando innovamos dejemos rastro de esto o lo publiquemos, lo que podemos hacer es entregar al inicio del curso un documento que refleje las innovaciones que se incorporarán en la asignatura, realizar cuestionarios con los alumnos donde den su opinión y realizar un informe para los directivos  de las novedades y resultados obtenidos durante la innovación.

Durante la innovación educativa convergen las metodologías usadas por el docente, como son: de evaluación, de la transmisión de conceptos, la acción tutorial, la aplicación del trabajo cooperativo, y los indicadores a ser usados, así como los paradigmas del docente, los paradigmas del aprendizaje y el uso de las nuevas tecnologías de la Información y Comunicación (TIC`s), incorporando diversas herramientas tales como la plataforma Moodle, el Web 2.0, el uso de blogs, wikis, redes sociales para la realización de trabajos colaborativos, software de aplicación como Power Point, Mindomo, Breeze, Cmaptools, etc.

Por último, puedo decir que es necesario que todo docente se actualice en las nuevas tecnologías (TIC`s), y use su creatividad para innovar en la práctica docente en beneficio del aprendizaje de los alumnos.

Forma Normal de Chomsky

Gramática ambigua.

Una sentencia w se denomina ambigua si puede obtenerse por más de un árbol de derivación (o equivalentemente, más de una derivación más a la izquierda o más a la derecha).

Una gramática G se denomina ambigua si el lenguaje que genera contiene alguna sentencia ambigua.

Lenguaje inherentemente ambiguo

Un lenguaje se denomina inherentemente ambiguo si no existe una gramática no ambigua que lo genere.

3.3 Formas Normales de Chomsky.

 Una GLC se dice que está en Forma Normal de Chomsky (FNC) si todas sus producciones son de la forma:

Excepcionalmente se permite la producción

 

La idea de la transformación de una gramática limpia a FNC se ejecuta en dos pasos:

·          

• Hacer que en la parte derecha de las producciones de longitud mayor o igual que dos sólo haya terminales.
• Trocear estas producciones para que tengan longitud dos.

Algoritmo FNC:

1. Para cada producción de la forma

(a) Para cada α_i, si α_i es terminal:

- Se añade la producción C_a → a

- Se cambia α_i por C_a en A → α₁..α_n

2. Para cada producción de la forma A → B1...B_m, m ≥ 3

(a) Se añaden (m-2) no terminales D₁, D₂, ..., D_m-2 (distintos para cada producción)

(b) La producción A → B₁...B_m se reemplaza por A → B₁D₁, D₁ → B₂D₂, ... D_m-2 → _Bm-1B_m

3.4 Forma Normal de Greibach

Definición:

Una GLC se dice que está en Forma Normal de Greibach (FNG) si todas sus producciones son de la forma:

 Excepcionalmente se permite la producción

 

¿Hasta qué profundidad deberíamos explorar el árbol de expansión para decidir si una cadena w de longitud n es generada o no por una gramática en FNC/FNG?

Nota:

Informaciòn recopilada de las siguientes ligas: 

http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte5.pdf

http://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r41963.PDF

José Miguel Puerta, Antonio Fernández Caballero, Departamento de Informática Universidad de Castilla-la Mancha en:

https://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r43399.PDF