diciembre 2013 - Api Developer: Lenguajes de Programación y Compiladores


POST


Post Top Ad

sábado, 7 de diciembre de 2013

Etapas de Compilación

jueves, 5 de diciembre de 2013

Ejemplos de Autómatas

12/05/2013 06:33:00 p.m. 0
Para la practicar la creación de autómatas, podemos trabajar los siguientes ejemplo en JFlap.

Se tiene un lenguaje de programación que tiene los siguientes componentes básicos:


a. Identificador letra(letra|digito)*
b. Real sin signo   digito+.digito+

c. Entero sin signo  digito+

d. Asignador   :=

e. Fin de sentencia  ;

f.  Suma    +




Nota: La función ungetc en algunos lenguajes se usa para regresar un espacio en el archivo.


Para un lenguaje de programación de expresiones lógicas considerar los siguientes elementos: 


a.  Identificador    letra(letra|digito)+

b.  Entero    digito+

c.  Suma     +

d.  Mayor que    >

e.  Mayor o igual que    >=

f.  Leer     READ

g.  Escribir    WRITE

h.  Si     IF

i.  Entonces    THEN 

j.  Paréntesis Izquierdo    (

k.  Paréntesis Derecho    )

l.  Fin de Sentencias    ;

m.  Asignador    =







Read More

miércoles, 4 de diciembre de 2013

Mini Manual de JFlap

12/04/2013 06:05:00 p.m. 1

DESCRIPCION Y DESCARGA DE JFLAP

JFlap es un programa creado en Java con el propósito de poder crear autómatas finitos deterministas y no deterministas, además de construir otros tipos como la máquina de Turing, gramáticas y expresiones regulares.

Puede encontrar JFlap en las siguientes direcciones:

Entre otras….

JFlap es un programa pre-compilado en Java, por lo que al descargarlo tendremos un único archivo .jar que podremos ejecutar fácilmente, pero es necesario tener instalada una versión de Java Development Kit (JDK, Virtual Machine). Esta plataforma es de uso libre, los archivos de actualizaciones o paquetes pequeños no instalan JDK.


ENTORNO DE JFLAP


Al ejecutar el programa estaremos en la siguiente ventana.

 


En donde podemos seleccionar el tipo de autómata que vamos a trabajar….En nuestro caso la primera adopción FiniteAutomaton.Vemos que se crea una nueva ventana para crear el autómata.



CREACION DE AUTOMATAS FINITOS (FINITE AUTOMATON)


Para crear un diagrama de moore utilizamos las siguientes opciones:

1.      Primero seleccione de la barra de menú la operación a realizar, por ejemplo: Para crear estados El círculo

2.      La flecha con punta rellena   es para seleccionar

3.      La otra flecha que apunta hacia la derecha   es para indicar las transiciones

4.      Y la calavera es para eliminar  .



Luego de haber agregado los estados, es el momento de indicar cuál es el estado inicial y final, para eso debe estar en modo selección, luego clic derecho del Mouse sobre el estado y observará el siguiente submenú:








Para crear una transición de un estado hacia el mismo, ubíquese en el estado y haga un doble clic.
  • Para probar el autómata, seleccione StepbyState del menú Input para evaluar carácter por carácter de la cadena digitada.
  • Digite la cadena:
  
  • Presione Aceptar para analizar la cadena de estado a estado (carácter por carácter).
  • El resultado es la siguiente ventana, donde debe dar clic sobre el botón Step para ir observando paso a paso la ejecución del autómata.

  • Dicha cadena deberá ser “aceptada” (verde) si se llega al estado final cumpliendo con las reglas del alfabeto (gramática) definida por el autómata (de estado a estado). Si un carácter no forma parte del alfabeto del autómata (si no es reconocido) o no cumple con las reglas entre un estado y otro, entonces la cadena es “rechazada” (rosado).
  • El autómata puede ser guardado, para ello utilizar el menú File y la opción Save / Save As.

Read More

martes, 3 de diciembre de 2013

Automatas de Estado Finito

12/03/2013 08:11:00 p.m. 0

Contenido

 

  • Conocer el concepto de los autómatas finitos
  • Conocer los tipos de autómatas finitos DFA y DNFA.
  • Funcionamiento de los autómatas finitos DFA
  • Funcionamiento de los autómatas finitos DNFA.
  • Ejemplos de autómatas finitos usando JFLAP

 

conceptos previos


Antes de crear los ejemplos mostrados debes haber leído la entrada sobre JFLAP, de manera de tener la respuesta para las siguientes preguntas.
  • ¿Qué es JFlap, como se instala y para qué se usa?
  • ¿Qué es JLex, cómo se instala y para qué se usa?
  • ¿Cómo implementar problemas de lenguajes formales según la jerarquía de Chomsky, con Jflap?
  • Qué son los autómatas finitos y autómatas de pila.

¿Qué es un autómata Finito?

 

  • Un  autómata  finito  es  un  conjunto  de  nodos  y  aristas  que  representan  trayectorias para generar una expresión bajo un alfabeto.
  • Undiagramadetransiciónesunautómata finito.


 

 

Elementos del Autómata Finito

 

  • Los estados se identifican dentro de un circulo.
  • El estado inicial recibe una flecha de transición que llega de ninguna parte.
  • Los estado aceptadores pueden identificarse con doble circulo o con una cruz(igual que signo +) al lado de ellos.
  • Las posibles transiciones se indicaran con flechas que van de un estado a otro, o incluso a sí mismos. Deben etiquetarse con el símbolo que produce el cambio de estado.


Los Estado del Autómata



  • Entonces decimos que los estado del autómata pueden ser:
  • Estados iniciales
  • Estados finales llamados aceptadores
  • Estados finales no aceptadores
  • La palabra que va de un estado a otro solo pertenece al lenguaje si el estado que la recibe es aceptador.
  • Y lo contrario, si llega al final hasta un estado no aceptador, la palabra no pertenece al lenguaje.  

EJEMPLO DE Autómata Finito

 


Supongamos que tenemos el siguiente ejemplo:


El lenguaje X es capaz de identificar la siguiente cadena.

w = aabab

Tratemos de identificar los procesos del Autómata.

Explicación del autómata:


1. Para comenzar estamos en el estado A, podemos llamarle estado 1. 
2. Hacemos la transición a B cuando leemos el símbolo a. 
3. Realizamos la siguiente transición de B hacia B porque leemos nuevamente otro símbolo a. 
4. Para leer b creamos otro estado D al que llegaremos desde donde estamos que es B.  
5. Para leer el siguiente símbolo que es a transferimos de nuevo hacia B. 
6. Luego para leer el siguiente símbolo b, el autómata regresa hasta D.

Representación de autómatas finitos con algorítmos


CLASIFICACIÓN DE LOS  AutómataS FinitoS 

 

Autómatas finitos determinísticos (DFA)



·  Es un dispositivo  que puede estar en un estado de entre un número finito de los mismos;  uno de ellos será el estado inicial y por lo menos uno será estado de aceptación

·  Tiene un flujo de entrada por el cual llegan los símbolos de una cadena que pertenecen a un alfabeto determinado. 

·  Se  detecta  el  símbolo  y  dependiendo  de  este  y  del  estado  en que  se  encuentre  hará  una  transición  a  otro  estado  o  permanece  en  el  mismo. 

·  El mecanismo de control o programa es que determina cual es la transición a realizar.
  


Ejemplo Autómatas finitos determinísticos (DFA)


Porqué se les llama autómatas finitos y porqué determinístico


Porqué finito:

Se refiere que hay un conjunto finito de estados.

Porque determinista: 

La  palabra  determinista  es  porque  el programa no  debe  tener ambigüedades,  es  decir,  en  cada  estado  solo  se  puede  dar  una  y  solo  una  (ni  dos  ni ninguna) transición para cada símbolo posible.

El autómata acepta la cadena de entrada si la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena. 
Si después del último símbolo la máquina no queda en estado de aceptación, se ha rechazado la cadena.

Tuplas de autómatas finitos 



El diagrama determinista estará caracterizado porque debe estar totalmente definido:

     Para cada estado solo debe salir un arco y solo uno para cada símbolo (el autómata no puede determinar la transición en el caso de que haya dos arcos con el mismo símbolo o no haya ninguno).

 Simbología de los autómatas finitos


Segundo ejemplo de autómatas finitos

·         El alfabeto S = { a, b, c }
·         Reconoce la cadena c
·         La cadena a
·         Las cadenas que empiezan   por a y acaban en a o en b y
·         Las que empiezan por a, seguidas de una serie de a ó de b y acaban en c





Entradas de Interés:

Read More
Derechos Reservados. Postecnologia.com. Con tecnología de Blogger.

Post Top Ad