Estudien Los Siguientes Conceptos

ESTUDIEN LOS SIGUIENTES CONCEPTOS

1-GRAMÁTICA LIBRE DE CONTEXTO.

En lingüística e informática, una gramática libre de contexto es una gramática formal en la que cada regla de producción es de la forma: V→w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto. Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la 4-tupla: G = (Vt,Vn,P,S) donde • • • • •

Vt es un conjunto finito de terminales Vn es un conjunto finito de no terminales P es un conjunto finito de producciones el denominado Símbolo Inicial los elementos de P son de la forma

Ejemplos [editar] Ejemplo 1 [editar] Una simple gramática libre de contexto es S → aSb | ε

donde | es un o lógico y es usado para separar múltiples opciones para el mismo no terminal, ε indica una cadena vacía. Esta gramática genera el lenguaje no regular .

Ejemplo 2 [editar] Aquí hay una gramática libre de contexto para expresiones enteras algebraicas sintácticamente correctas sobre las variables x, y y z: S → x | y | z | S + S | S - S | S *S | S/S | (S) Generaría, por ejemplo, la cadena (x + y) *x - z *y / (x + x)

Ejemplo 3 [editar] Una gramática libre de contexto para un lenguaje consistente en todas las cadenas que se pueden formar con las letras a y b, habiendo un número diferente de una que de otra, sería: S→U|V U → TaU | TaT V → TbV | TbT T → aTbT | bTaT | ε T genera todas las cadenas con la misma cantidad de letras a que b, U genera todas las cadenas con más letras a, y V todas las cadenas con más letras b.

Ejemplo 4 Otro ejemplo para un lenguaje es . No es un lenguaje regular, pero puede ser generado por la siguiente gramática libre de contexto. S → aSc | B B → bBc | ε

Otros ejemplos Las gramáticas libres de contexto no están limitadas a lenguajes matemáticos formales. La gramática de Lojban, un lenguaje artificial hablado con gran capacidad expresiva, es también libre de contexto y no ambiguo. El lingüista indio Pánini describió el sánscrito usando una gramática libre de contexto. Recientemente se ha sugerido que una clase de poesía Tamil llamada Venpa utiliza principalmente una gramática libre de contexto.

EJEMPLO DE DCG (Definite Clause Grammars) *ojo, estudien más de uno.

A definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs. They are called definite clause grammars because they represent a grammar as a set of definite clauses in first-order logic. The term DCG refers to the specific type of expression in Prolog and other similar languages; not all ways of expressing grammars using definite clauses are considered DCGs. However, all of the capabilities or properties of DCGs will be the same for any grammar that is represented with definite clauses in essentially the same way as in Prolog. The definite clauses of a DCG can be considered a set of axioms where the validity of a sentence, and the fact that it has a certain parse tree can be considered theorems that follow from these axioms[1]. This has the advantage of making it so that recognition and parsing of expressions in a language becomes a general matter of proving statements, such as statements in a logic programming language.

Example A basic example of DCGs helps to illustrate what they are and what they look like. sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats].

This generates sentences such as "the cat eats the bat", "a bat eats the cat". One can generate all of the valid expressions in the language generated by this grammar at a Prolog interpreter by typing sentence(X,[]). Similarly, one can test whether a valid sentence in the language by typing something like sentence([the,bat,eats,the,bat],[]).

[edit] Translation into definite clauses DCG notation is just syntactic sugar for normal definite clauses in Prolog. For example, the previous example could be translated into the following: sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3). noun_phrase(S1,S3) :- det(S1,S2), noun(S2,S3). verb_phrase(S1,S3) :- verb(S1,S2), noun_phrase(S2,S3). det([the|X], X).

det([a|X], X). noun([cat|X], X). noun([bat|X], X). verb([eats|X], X).

[edit] Difference lists The arguments to each functor, such as (S1,S3) and (S1,S2) are difference lists; difference lists are a way of representing a list as the difference of two lists. Using Prolog's notation for lists, a list L can be represented with the pair ([L|X],X). Difference lists are used to represent lists with DCGs for reasons of efficiency. It is much more efficient to concatenate difference lists, in the circumstances that they can be used, because the concatenation of (S1,S2) and (S2,S3) is just (S1,S3).[11]

[edit] Non-context-free grammars Normal DCG rules with no extra arguments on the functors, such as the previous example, can only express context-free grammars; there is only one argument on the left side of the production. However, context-sensitive grammars can also be expressed with DCGs, by providing extra arguments, such as in the following example: s --> a(N), b(N), c(N). a(0) --> []. a(M) --> [a], a(N), {M is N + 1}. b(0) --> []. b(M) --> [b], b(N), {M is N + 1}. c(0) --> []. c(M) --> [c], c(N), {M is N + 1}.

This set of DCG rules describes the grammar which generates the language that consists of n n n strings of the form a b c .[12]

[edit] Representing features Various linguistic features can also be represented fairly concisely with DCGs by providing extra arguments to the functors.[13] For example, consider the following set of DCG rules: sentence --> pronoun(subject), verb_phrase. verb_phrase --> verb, pronoun(object). pronoun(subject) --> [he]. pronoun(subject) --> [she]. pronoun(object) --> [him]. pronoun(object) --> [her]. verb --> [likes].

This grammar allows sentences like "he likes her" and "he likes him", but not "her likes he" and "him likes him".

[edit] Parsing with DCGs

An example parse tree for this grammar.

The main practical use of a DCG is to parse sentences of the given grammar, i.e. to construct a parse tree. This can be done by providing "extra arguments" to the functors in the DCG, like in the following rules: sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP). noun_phrase(np(D,N)) --> det(D), noun(N). verb_phrase(vp(V,NP)) --> verb(V), noun_phrase(NP). det(d(the)) --> [the]. det(d(a)) --> [a]. noun(n(bat)) --> [bat]. noun(n(cat)) --> [cat]. verb(v(eats)) --> [eats].

One can now query the interpreter to yield a parse tree of any given sentence: | ?- sentence(Parse_tree, [the,bat,eats,a,cat], []). Parse_tree = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(bat)))) ? ;

2.-PREDICADOS DINÁMICOS DE PROLOG Predicados dinámicos Una de las características más útil de Prolog es la posibilidad de añadir y eliminar cláusulas de los predicados presentes en el programa, y hacerlo en tiempo de ejecución. Los predicados con esta posibilidad se denominan predicados dinámicos.

Declaración de predicados dinámicos Estos predicados deben ser previamente marcados mediante la directiva dynamic/1, indicando el nombre del predicado dinámico. El siguiente ejemplo declara el predicado prueba/1 como dinámico. Por lo demás, un predicado dinámico es como otro cualquiera excepto en que puede no tener cláusulas. En ese caso, una llamada al predicado simplemente falla, pero no provoca un error de predicado indefinido.

:- dynamic prueba/1. prueba(abc). prueba(123).

Añadiendo cláusulas Para insertar cláusulas de un predicado dinámico existe una familia de predicados ISO-standard, la familia assert, consistente en los siguientes predicados:

asserta/1

Inserta una nueva cláusula como si se hubiera escrito al principio del programa.

assertz/1

Inserta una nueva cláusula como si se hubiera escrito al final del programa.

assert/1 Idéntico a asserta/1. La diferencia entre insertar las cláusulas por el principio o por el final es muy importante puesto que determina el orden de sucesión de las soluciones. El argumento que toman estos predicados es la nueva cláusula a insertar, pero teniendo en cuenta lo siguiente:

• • •

Las variables ligadas dentro de la cláusula se sustituyen por su valor en el momento de insertar dicha cláusula. Esto es lo lógico y deseable. Las variables libres dentro de la cláusula se sustituyen por variables nuevas en el momento de la inserción. Es decir, posteriores unificaciones no afectan a la cláusula ya insertada. Si existen puntos de elección para el predicado modificado (aquel para el que se inserta una nueva cláusula), estos se mantienen y no se generan nuevos puntos de elección. Es decir, la nueva cláusula no se tendrá en cuenta hasta que se ejecute un nuevo objetivo para el predicado en cuestión.

Como ejemplo veamos como insertar cláusulas en el predicado prueba/1. Antes recordemos las cláusulas que ya existen, en orden: prueba(abc). prueba(123).

Ahora añadimos una cláusula ejecutando asserta(prueba(666)). El programa queda como sigue: prueba(666). prueba(abc). prueba(123).

De nuevo añadimos una cláusula ejecutando J=999,assertz(prueba(J)). El programa queda como sigue: prueba(666). prueba(abc). prueba(123). prueba(999).

Y para finalizar generamos una cláusula algo mas compleja mediante assertz( (prueba(X) :- X>1024) ) ... prueba(666). prueba(abc). prueba(123). prueba(999). prueba(H) :H > 1024.

Eliminando cláusulas Análogamente, es posible eliminar cláusulas de predicados dinámicos mediante la familia de predicados retract consistente en:

retract/1

Elimina únicamente la primera cláusula que unifique con el argumento. Siempre se elimina por el principio del programa.

rectractall/1 Elimina todas las cláusulas que unifiquen con el argumento. De nuevo, hay que considerar que:

• • • •

Los puntos de elección que ya existieren a causa de las cláusulas eliminadas permanecen mientras sea necesario. retract/1 es constructivo. Las variables libres se ligan a los elementos de la cláusula eliminada. retract/1 tiene tantas soluciones como cláusulas existan que unifiquen con el argumento. Es decir, si se hace backtracking sobre él, se eliminan todas las cláusulas que unifiquen. Falla cuando no hay más cláusulas a unificar. retractall/1 solamente tiene una solucion, y no es constructivo. No liga las variables libres.

En el siguiente ejemplo se observa el funcionamiento de assert y retract. ?- asserta(ejemplo(i(k))). yes ?- asserta(ejemplo(i(l))). yes ?- asserta(ejemplo(j(X))). yes ?- assertz(ejemplo(j(2))). yes ?- assertz(ejemplo(j(8))). yes ?- ejemplo(X),display(ejemplo(X)),nl,fail. ejemplo(j(_510)) ejemplo(i(l)) ejemplo(i(k)) ejemplo(j(2)) ejemplo(j(8)) no ?- retractall(ejemplo(i(X))). yes ?- ejemplo(X),display(ejemplo(X)),nl,fail. ejemplo(j(_510)) ejemplo(j(2)) ejemplo(j(8)) %% -- Nota -%% Aqui provocamos el backtracking pidiendo %% otra solucion. no ?- retract(ejemplo(j(X))).

yes ?- retract(ejemplo(j(X))). X = 2 ? ; X = 8 ? ; no ?-

Finalidad de los predicados dinámicos El lector se preguntará qué finalidad tiene la propiedad tan espantosa de modificar el código. Haciendo un mal uso de los predicados dinámicos solamente provocamos ilegibilidad del programa, dificultad para realizar trazas, efectos laterales y otras desgracias. El único uso legítimo es la implementación de estado en los programas Prolog. Supongamos que necesitamos un programa que controle la temperatura de una sala: :- dynamic temperatura/1. temperatura(23). sensor_temperatura :esperar(10), leer_temperatura(NuevaTemperatura), rectract(temperatura(_AnteriorTemperatura)), assert(temperatura(NuevaTemperatura)), !, sensor_temperatura.

Sin assert/retract no sería posible almacenar el estado del sensor de temperatura. En general, solamente deberían ser predicados dinámicos aquellos que almacenan hechos simples, es decir, aquellos cuyas cláusulas no tienen cuerpo.

Ejemplo El siguiente ejemplo implementa una pila de datos al estilo imperativo mediante assert/retract. :- module(pila,[],[]). :- export(push/1). :- export(pop/1). :- dynamic datos/1. push(NuevoDato) :asserta(datos(NuevoDato)). pop(Dato) :retract(datos(Dato)), !.

Para implementar una cola en lugar de una pila bastaría con sustituir asserta por assertz.

Nota sobre la coherencia lógica de los programas Ya hemos mencionado anteriormente el efecto de los predicados assert/retract sobre los puntos de elección en el programa, sin embargo, vamos a insistir un poco más sobre esto.

Decimos que un programa tiene coherencia lógica cuando hace exactamente lo que dice el programa escrito. Pero los predicados dinámicos podrían, en principio, provocar comportamientos inexplicables en un programa. Veamos un ejemplo, el siguiente programa consiste en un bucle de fallo. Lo que dice el programa es que se hace backtracking sobre el predicado test/1, que tiene un número finito de soluciones. Por tanto es un programa finito. Hemos numerado las lineas del programa que nos interesan. test(sol1). test(sol2). main :test(X), display(X), nl, asserta(test(sol)), fail.

%% %% %% %%

Linea Linea Linea Linea

1 2 3 4

Ahora supongamos que asserta/1 no respetase los puntos de elección. Ocurriría lo siguiente:

• • • • • • •

LLegamos al objetivo test(X) en la línea 1. Se insertan dos puntos de elección. Se elimina el punto de elección 1 y ejecuta la linea 2. La línea 3 inserta un tercer punto de elección. La línea 4 provoca el backtracking. El backtracking se para en la linea 1, eliminando el punto de elección 2. La linea 3 inserta un cuarto punto de elección. Se repite de nuevo el backtracking, pero ahora hay un tercer punto de elección, luego se repite otra vez todo el proceso.

El programa resulta infinito porque asserta/1 no para de insertar puntos de elección. Pero eso no es lo que dice el programa. Afortunadamente, assert/retract no modifican los puntos de elección hasta que no se han eliminado todos los que existieran previamente del predicado afectado. Por eso, la ejecución de main/1 llevaría al siguiente resultado: ?- main. sol1 sol2 yes ?-

Solamente, al ejecutar main/1 por segunda vez encontramos un resultado distinto: ?- main. sol sol1 sol2 yes ?-

Esto es lo que se denomina mantener la coherencia lógica del programa. Es decir, no se permite que un programa se modifique a sí mismo hasta que no termine de ejecutarse la parte afectada.

3.- SISTEMAS EXPERTOS

Un Sistema Experto es una aplicación informática que simula el comportamiento de un experto humano, en el sentido de que es capaz de decidir cuestiones, aunque sea en un campo restringido. Para esto, se debe tener en cuenta que la principal característica del experto humano viene a ser el conocimiento o habilidades profundas en ese campo concreto, por consiguiente, un Sistema Experto debe ser capaz de representar ese conocimiento profundo con el objetivo de utilizarlo para resolver problemas, justificar su comportamiento e incorporar nuevos conocimientos. Se podría incluir también el hecho de poder comunicarse en lenguaje natural con las personas, aunque esta capacidad no es tan determinante como las anteriores de lo que se puede definir como Sistema Experto.  Interfaz de usuario El mecanismo que permite la comunicación entre el usuario y el sistema experto  Medio de explicación Explica al usuario el razonamiento del sistema. Es el que permite justificar y explicar el análisis completo del problema y las soluciones propuestas, así como la semejanza o diferencia entre dicha solución y las de los casos históricos.  Memoria activa: Una base de datos global de los hechos usados por las reglas  Mecanismo de inferencia: Hace inferencias al decidir cuales reglas satisfacen los hechos u objetos, da prioridad a las reglas satisfechas y ejecuta la regla con la prioridad más elevada  Agenda Una lista con prioridades asignadas a las reglas, creada por el mecanismo de inferencia, cuyos patrones satisfacen los hechos u objetos de la memoria activa. La pila de objetivos en la resolución lineal  Medio para la adquisición de conocimiento Vía automática para que el usuario introduzca conocimientos en el sistema, sin tener al ingeniero del conocimiento para qué codifique este en forma explícita. El módulo de adquisición del conocimiento permite que se puedan añadir, eliminar o modificar elementos de conocimiento (en la mayoría de los casos reglas) en el sistema experto. Si el entorno es dinámico es muy necesario, puesto que, el sistema funcionará correctamente sólo si se mantiene actualizado su conocimiento. El módulo de adquisición permite efectuar ese mantenimiento, anotando en la base de conocimientos los cambios que se producen [CHAP]. Todos los conocimientos que se obtienen deben ser estructurados de una forma correcta, todo este conocimiento se almacena en lo que se conoce como la base de conocimientos OJO: LES ANEXO UNA PRÁCTICA CON UN SISTEMA EXPERTO PARA QUE LO CAPTUREN EN EL SWI PROLOG Y LO CORRAN, VEAN COMO FUNCIONA.

4.- ÁRBOL SLD. SLD (Selection Linear Definite) Aplicar la regla de Selección de cláusulas (el orden de las cláusulas es de arriba hacia abajo, o sea como están en la base interna de predicados de prolog y la selección de objetivos es de izquierda a derecha), posteriormente la resolución Lineal (que vimos en clase) sobre un conjunto de cláusulas Definidas (las que forman los programas). La idea entonces, es aplicar la resolución lineal que vimos en clase y graficarla como árbol. Ejemplos: Cláusulas Definidas (o sea el programa) p(X,Z):- q(X,Y), p(Y,Z). p(X,X). q(a,b). Objetivo (goal) ?- p(X,b). **Entonces armamos el árbol SLD asumiendo que la estrategia de selección de átomos es de izquierda a derecha (seleccionamos el de más a la izquierda)

Ejemplo 2 Cláusulas definidas:

alumno(A,P):- estudia(A,C), enseña(P,C). estudia(ana, ia). estudia(ana,pl). estudia(eva,ra). enseña(jose_a, ia). enseña(jose_a, ra). enseña(Rafael,pl). Consulta (goal). ?- alumno(A, jose_a). ARBOL SLD.

NOTAS: -LAS HOJAS REPRESENTAN CASOS DE ÉXITO Y FALLO, EN CASO DE ÉXITO LA HOJA DEBERÁ TENER EL UMG CON ELCUAL LA CONSULTA SE HACE VERDADERA. -ES COMO EJECUTAR EL GOAL (OBJETIVO) DE MANERA EXHAUSTIVA, COMO SI DESPUES DE LA PRIMERA RESPUESTA, PREGUNTÁRAMOS OTRA VEZ CON “;” Y VOLVIÉSEMOS A APLICAR EL MECANISMO DE RESOLUCIÓN LINEAL CON UNIFICACIÓN QUE VIMOS EN CLASE. 5.- Ordenamiento de listas. Estudien los algoritmos que dejamos en clase, más el mergesort y burbuja mejorado. 6.- Recuerden que en prolog las estructuras de control para realizar iteración (que son parte esencial de los lenguajes estructurados) no existen, en su lugar obligamos a la máquina de inferencias a iterar por medio de los predicados de tipo……? 7.- SEMÁNTICA DE PROGRAMAS LÓGICOS

La semántica del sistema establece correspondencias entre los componentes sintácticos y los elementos, propiedades y relaciones de un mundo. Estas correspondencias permiten interpretar un programa lógico de tal forma que a cada fórmula se le pueda asignar un valor de verdad (verdadero o falso). Si la interpretación que se da a un programa lógico hace verdaderas a todas las fórmulas del programa, se dice que dicha interpretación es un modelo del programa  Cuando el programa lógico tiene al menos un modelo, el conjunto de fórmulas que lo constituyen es satisfacible.  Debido al tipo de expresiones consideradas, se restringe a cláusulas definidas y dado que éstas no contienen negaciones, resulta imposible que un programa lógico este compuesto por un conjunto insatisfacible de fórmulas, ya que, de un programa no se podrá deducir una fórmula y su negación, es decir, no se podrán deducir contradicciones.  En consecuencia siempre existirá un modelo que hará verdadero al programa lógico. Además, siempre existirá un modelo mínimo que reflejará la información expresada única y exclusivamente por el programa