RESUMEN DE SINTAXIS Y SEMANTICA DE LOS LENGUAJES.

Capitulo 1: Lenguajes.

Alfabeto-Vocabulario (V): Conjunto finito de símbolos.

Cadena-Tira-String (S): Secuencia finita de símbolos sobre un alfabeto, es decir, tomados de un

alfabeto.

Longitud de una cadena |S|: Cantidad de ocurrencias de los símbolos en la cadena.

Cadena vacía: cadena que tiene longitud 0. Se representa con el símbolo є => |є| = 0.

Prefijo de una cadena S: es toda cadena que se obtiene eliminando 0 o más símbolos desde la

derecha de la cadena S. La cadena S es un prefijo de sí mismo. Є también es un prefijo de la cadena

S.

Sufijo de una cadena S: es toda cadena que se obtiene eliminando 0 o más símbolos u ocurrencia

de símbolos desde la izquierda de la cadena S.

Subcadena de la cadena S: es toda cadena que se obtiene suprimiendo un prefijo y un sufijo de la

cadena S. la cadena S y є también son subcadenas de la cadena S.

Subsecuencia de una cadena S: es toda cadena formada por la eliminación de 0 o más símbolos, no

necesariamente consecutivos, de la cadena S.

V*: es un conjunto infinito. Representa el conjunto de diferentes cadenas posibles de un alfabeto.

Є pertenece a a.

Lenguaje sobre un alfabeto V: es todo conjunto de cadenas construidos con símbolos del alfabeto

V. cualquier subconjunto de V* es un lenguaje sobre el alfabeto V. є no es un lenguaje pero si lo es

{є}. V* también es un lenguaje al igual que ø.

Operaciones sobre cadenas:

• Concatenación: siendo x e y dos cadenas, su concatenación produce una cadena z formada

por xy.

• Potencia entera positiva de S: se define { so = є

Sn = S

n-1 * S (para toda n >0)}

Operaciones sobre lenguajes:

• Unión: siendo L y M lenguajes sobre V*. L U M={s | s en L o M}

• Concatenación: siendo L y M dos lenguajes cobre V*. L.M = {s=r.t | r є L ^t є M}

• Potencia entera positiva de un lenguaje L: se define { L0 = { є}

Ln = L

n-1.L (para toda L>0)

• Cerradura o clausura de Kleene de un lenguaje L: L*= L0UL

1UL

2U…=

i

• Cerradura o clausura positiva de un lenguaje L: L+= L

1UL

2U…=

i

Capitulo 2: Expresiones regulares.

Reglas de definición de las expresiones regulares:

Quedan definidas mediante 3 reglas:

1. Є es una expresión regular. Representa al conjunto regular o al lenguaje regular {є}.

2. Si a esta en є, entonces a es una expresión regular. Representa al lenguaje regular {a}.

3. Si s y t son expresiones regulares, las que representan a los lenguajes L(s) y L(t)

respectivamente entonces:

1. (s)|(t) es una expresión regular la cual representa al

lenguaje L(s)UL(t).

2. (s).(t) es una expresión regular la cual representa al

lenguaje L(s).L(t)

3. (s)* es una expresión regular que representa al lenguaje

(L(s))*

4. (s) es una expresión regular que representa al lenguaje

L(s).

Equivalencias entre expresiones regulares (er)

Se define equivalencia entre e.r. (r=s) si r y s representan al mismo lenguaje.

Propiedades algebraicas de las expresiones regulares (er)

a) r|s=s|r (conmutativa)

b) (r|s)|t=r|(s|t) (asociativa)

(r.s).t=r.(s.t)

c) (r|s).t=r.t|s.t (distributiva)

r.(s|t)=r.s|r.t

d) Є.r=r. є=r (elemento neutro)

r*=(r| є)*

e) r**=r* (ídem potencia)

Definiciones regulares

Una definición regular es una secuencia de definiciones de la siguiente forma:

Nombre designa

� er.

Operaciones adicionales

• “1 o más veces” (+)

r�L (r)

(r)+�(L(r))

+

• “0 o más veces”

(r)? � L(r)U{ є}

Propiedades

r*=r+| є

r+=r.r*

r?=r| є

Capitulo 3 Gramáticas.

Una gramática es un conjunto de cuatro elementos

G{Vn;Vr;P;S}

Vn: Conjunto finito de símbolos llamados no-terminales, es decir, que en un alfabeto de símbolos

no-terminales (variables sintácticas). Se representa con letras mayúsculas.

Vr: alfabeto de símbolos terminales. Se representa con minúsculas y dígitos.

Vn Vr=

VnUVr=V (alfabeto de símbolos gramaticales).

P: Conjunto finito de “producciones”

Forma general: α�β (alfa produce beta)

α en V+

β en V*

S: símbolo START o raíz S en Vn

En las producciones debe existir uno donde α sea S.

Lenguaje generado por una gramática

Definición: derivación en un paso (�): δασ�δβσ.

δ y σ son cadenas arbitrarias de símbolos gramaticales (δ,σ en v*)

Existe un producción en α�β en P

Derivación en n pasos:

δ0�δ1� δ2�…� δn

�* derivación en 0 o más pasos

�+ derivación en 1 o más pasos

Frases de una gramática

L(G)={w/w en Vt* y S�+ w}

Se llama frase de la gramática a toda cadena del lenguaje generado por la gramática.

Se llama forma de frase de la gramática a toda cadena δ| δ en V* que representa al menos un no-

terminal y deriva en 0 o más pasos de δ (δ�* δ)

Tipos de gramática

• Tipo 0: “de estructura de fase”. Es el caso más general. Todas las gramáticas que existen

son de este tipo.

• Tipo 1: “sensible al contexto” α�β es |β| |α|

• Tipo 2: ”independiente del contexto” α�β es α en Vn.

• Tipo 3: “regulares” α�β α en Vn

Β toma la forma a o aA con a en Vr y A en Vn

Reconocedor de un lenguaje

Dado un lenguaje determinado, un reconocedor de ese lenguaje es una maquina. Se le entrega

una cadena de símbolos. La maquina analiza y devuelve SI o NO. SI cuando está en el lenguaje y

NO cuando la cadena no está en el lenguaje.

Capitulo 4 Autómatas finitos de estado

Son los reconocedores naturales de los lenguajes regulares. Estudiaremos un método para

obtener el autómata de un lenguaje regular partiendo de la expresión regular que representa al

lenguaje.

Se clasifican en : determinísticos (AFD) y no deterministicos (AFN)

AFN: Es un modelo matemático formado por:

• Un conjunto finito S de estado

• Un conjunto finito V de símbolos de entrada

• Un estado S0 llamado estado inicial

• Un conjunto finito F de estados de aceptación o

estados finales.

• Una función “mueve” / a cada par estado-símbolo

le hace corresponder un conjunto de estados.

Una AFN se puede representar mediante un grafo dirigido y etiquetado llamado grafo de

transiciones. Los estados quedan representados por los nodos y la función “mueve” queda

representada por las etiquetas de aristas que conectan los nodos.

Los estados de aceptación se representan con un doble círculo.

Se dice que un AFN “acepta” una cadena de entrada X si y solo si hay algún camino en el grafo de

transiciones entre S0 y algún estado de aceptación, tal que, concatenando las etiquetas de los

sucesivas aristas a lo largo del camino resulta X.

Un autómata finito deterministico (AFD) es un caso especial del AFN en el cual se dan los

siguientes hechos:

• No tiene transiciones є.

• Para cada estado S y cada símbolo de entrada a, hay a lo sumo una arista

etiquetada con a que sale de S.

Obtención de un AFD equivalente a un AFD dado.

Después de leer la entrad (a1,a2,a3,a4,…,an) el AFD se encuentra en un estado que representa al

subconjunto de los estados del AFN alcanzados del estado inicial del AFN por medio de un camino

etiquetado con a1,a2,a3,a4,…,an.

El AFD simula “en paralelo” todos los posibles caminos que el AFN puede realizar con una

determinada cadena de entrada.

S: estado de AFN.

T: conjunto de estados de AFN.

a: símbolo de entrada al AFN.

cerr- є (S): conjunto de estados del AFN alcanzables desde el estado S con transiciones є.

cerr- є (T): conjunto de estados de AFN alcanzables desde los estados de T con solo transiciones є.

mueve-(T,a): da el conjunto de estados del AFN hacia los cuales hay una transición con el símbolo

“a” desde algún estado de T.

Dos cadenas distinguibles.

Se dice que la cadena W distingue al estado s del estado t si, comenzando con el AFD en el estado

s y alimentándolo con la cadena W, se termina en un estado de aceptación, mientras que

comenzando con el AFD en el estado t y alimentándolo con la misma entrada W, se termina en un

estado de no aceptación, o viceversa.

La idea principal de optimización es obtener una partición del conjunto de estados S que tenga las

siguientes propiedades:

1. Dos estados cualesquiera pertenecientes a una misma parte son estados indistinguibles

(no existe cadena alguna que los distinga).

2. Dos estados cualesquiera pertenecientes a dos partes distintas son estados distinguibles

(alguna cadena los diferencia).

Método de minimización.

• Obtenida la partición indicada, por cada parte de ese, se elije un estado representante, estos

estados serán los estados del AFD optimo.

• Si con un símbolo determinado “a” , todos los estados de una parte conducen a estados de

otra, entonces en el AFD óptimo se establece una transición entre el representante de la

primera parte y el estado representante de la otra parte.

• Estado inicial del AFD optimo � representante de la otra parte que tiene al estado inicial del

AFD inicial original.

• Estados de aceptación del AFD óptimo son aquellos representantes que son estados de

aceptación del AFD original.

• Si aparece algún estado inactivo (que no sea de aceptación y que tenga transiciones hacia el

mismo con todos los símbolos ) ese estado debe eliminarse.

Autómatas Push-Down.

La clase de lenguajes generados por Gramáticas libres de contexto (GLC) es más amplia que la

clase de lenguajes definidos por Expresiones regulares. Todos los lenguajes regulares pueden ser

generados por GLC, como así también algunos lenguajes no regulares ({a a la n b a la n} y los

Palíndromos).

Para cada lenguaje regular hay al menos una maquina que funciona exitosamente solo sobre las

cadenas de entrada de ese lenguaje y para cada maquina, el conjunto de palabras que acepta es

un lenguaje regular.

Debe haber al menos una maquina que acepta cada GLC y el lenguaje aceptado por cada maquina

es libre de contexto.

Cinta de entrada: debe ser suficientemente larga para aceptar cualquier posible entrada, y ya que

cualquier palabra en a* es una posible entrada, la CINTA debe ser infinitamente larga.

START: el estado START es donde se comienza. Lo único q hace es dar inicio al proceso y enviarnos

directamente al próximo estado. Un estado START no tiene flechas ingresando a el.

ACCEPT: es el estado de aceptación, entra este estado y no se puede salir. Es un estado de

detención.

REJECT: un estado reject es un estado de detención que no es un final aceptable.

READ: es la tarea mas importante desarrollada por un estado en un AF es leer una letra de

entrada y saltar a otros estados dependiendo de que letra ha sido leída.

PUSHDOWN STACK: es un lugar en el que las letras de entrada puede almacenarse hasta que

queramos referirnos a ellas nuevamente.

PUSH: la operación PUSH agrega una nueva letra a la línea. La nueva letra es colocada en tope del

STACK y todas las demás letras son empujadas abajo o atrás. Antes que la maquina comience a

procesar una cadena de entrada el STACK se presume que esta vació lo que significa que cada

ubicación de almacenamiento en el mismo contiene un blanco.

POP: es la instrucción para tomar una letra y sacarla del STACK. Esto causa que la letra que esta

mas arriba en el STACK sea sacada del mismo. El resto de las letras son movidas una posición hacia

arriba cada una. Un STACK PUSH DOWN es llamado un archivo LIFO (last in first out).

AUTOMATA PUSH-DOWN: cuando un AF ha sido expandido con un STACK y los estados PUSH y

POP. Los APD son la maquinas que necesitamos para reconocer GLC. Toda GLC puede ser definida

como un lenguaje aceptado por algún APD y el lenguaje aceptado por algún APD puede ser

definido por alguna GLC. Hay dos tipos de APD:

• APD DETEMINISTA es tal que para toda

cadena de entrada tiene un único camino a

través de la maquina.

• APD NO DETERMINSTA es aquel en el que en

determinadas ocasiones tendremos que

elegir entre diferentes posibles caminos a

través de la maquina.

Definición de un autómata push –down (APD) es una colección de 8 cosas:

1. Un alfabeto Σ de letras de entrada.

2. Una cinta de entrada (infinita de una dirección).

3. Un alfabeto Γ de caracteres del STACK.

4. Un STACK pushdown, que inicialmente esta vació.

5. Un estado START.

6. Estados de detención de dos clases: algunos ACCEPT y algunos REJECT.

7. Un número finito de estados PUSH.

8. Un numero finito de estados con ramificación (READ y POP).

Maquinas de Turíng.

Lenguaje definido por: Aceptor correspondiente Ejemplo de aplicación

Expresión Regular

autómata Finito

Grafo de Transición

Editores de Texto,

Circuitos Secuenciales

Gramática Libre de Contexto autómata PushDown

Sentencias de lenguajes de

programación.

Compiladores

Gramática de tipo 0

Maquina de Turing

Maquina de Post

Computadoras

Definición:

Una maquina de Turing, denotada MT, es una colección de seis cosas:

1. Un alfabeto Σ de letras de entrada.

2. una CINTA dividida en una secuencia de celdas numeradas, esta contiene la palabra de

entrada y el resto se completa con blancos.

3. Una CABEZA de CINTA que puede en un paso leer el contenido de una celda de la CINTA,

reemplazarlo con algún otro carácter, y reposicionarse en la próxima celda a la derecha o a la

izquierda de aquel que ha sido recién leído.

4. Un alfabeto Γ, de caracteres que pueden ser impresos en la CINTA por la CABEZA de CINTA.

5. Un conjunto finito de estados que incluye exactamente un estado START desde el cual

comienzo la ejecución (y en el que podemos reingresar durante la ejecución) y algunos (quizás

ninguno) estados de HALT que causan que la ejecución termine cuando se ingresa en ellos.

6. Un programa que es un conjunto de reglas que nos dicen, en base a la letra que la CABEZA de

CINTA ha leído, como cambiar de estado, que imprimir, donde mover la CABEZA de CINTA.

Diseñamos al programa como una colección de aristas direccionalas que conectan estados.

Cada arista esta etiquetada con un triplete de información (letra, letra, dirección).

• La primera letra es el carácter que la CABEZA de CINTA lee desde la celda a la que esta

apuntando.

• La segunda letra es la que la CABEZA de CINTA imprime en a celda antes de dejarla.

• El tercer componente, la dirección, le dice a la CABEZA de CINTA si moverse una celda

a la derecha, R, o una celda a la izquierda, L.

Todas las maquinas de Turing son deterministas. Esto significa que no hay un estado que tenga dos

o más aristas que salen de el etiquetadas con la misma primera letra.

Compiladores.

Un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo

traduce a un programa equivalente en otro lenguaje, el lenguaje objeto.

Modelo de analisis y síntesis de la compilación.

En la compilación hay dos partes: analisis y síntesis. La parte del analisis divide al programa fuente

en sus elementos componentes y crea una representación intermedia del programa fuente. La

parte de la síntesis construye el programa objeto deseado a partir de la representación

intermedia.

Durante el analisis, se determinan las operaciones que implica el programa fuente y se registran

en una estructura jerarquica llamada arbol.

El contexto de un compilador.

Un programa fuente se puede dividir en modulos almacenados en archivos distintos. La tarea de

reunir el programa fuente a menudo se confia a un programa distinto, llamado preprocesador.

El programa objeto creado por el compilador puede requerir procesamiento adicional antes de

poderlo ejecutar.

Analisis del programa fuente.

En la compilación, el analisis consta de tres fases:

1. Analisis lineal (analisis lexico), en el que la cadena de caracteres que constuye el programa

fuente se lee de izquierda a derecha y se agrupa en componentes lexicos, que son

secuencias de caracteres que tienen un significado colectivo.

2. Analisis jerarquico (analisis sintactico), en el que los caracteres o los componentes lexicos

se agrupan jerárquicamente en colecciones anidadas con un significado colectivo.

3. Analisis semantico, en el que se realizan ciertas revisiones para asegurar que los

componentes de un programa se ajustan de un modo significativo.

Sistema para procesamiento de un lenguaje.

Poner el diagrama.

Las fases de un compilador.

poner el diagrama