Autómatas Finitos Deterministas y Lenguajes Formales

60 %
40 %
Information about Autómatas Finitos Deterministas y Lenguajes Formales
Education

Published on March 21, 2014

Author: sandyrafaelgarcia

Source: slideshare.net

Autómatas Finitos Deterministas – Lenguajes Formales Sandy Rafael Garcia Mateo Jeffry Gonzalez Garcia Prof. Rina Familia

Temas a tratar • Autómata Finito Determinista • Definición Formal de AFD • Lenguajes Regulares • Propiedades de los lenguajes regulares

Autómata finito determinista • El lenguaje que acepta un AFD(Autómata Finito Determinista) es el conjunto de palabras definidas sobre Σ(un alfabeto) que hacen que el autómata llegue a un estado final de aceptación.

Definición Formal

Lenguajes Regulares • Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y estrella de Kleene un número finito de veces. • Tomaremos el siguiente modelo, como base para ejemplificar las diferentes operaciones.

Lenguajes Regulares • Ejemplo, modelo base: • Suponiendo que los dos autómatas siguientes sean para el mismo alfabeto Σ = { x, y }:

Unión • La unión de dos lenguajes regulares es otro lenguaje regular. Se utiliza la operación de unión de conjuntos; así, para el alfabeto Σ ={x,y} si L1 = {x,xy} y L2 = {yz,yy} entonces su unión será L1 È L2 = {x,xy,yz,yy }.

Propiedades de Unión

Unión – Ejemplo

Concatenación • Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda).

Propiedades de Concatencación

Concatenación – Ejemplo

Estrella de Kleene • La estrella de Kleene de cualquier lenguaje regular también es regular. Se caracteriza por que se utiliza solo un lenguaje en lugar de dos. Se logra formando todas las concatenaciones de cero (cadena vacía) o más cadenas del lenguaje que se amplía. La operación se representa con el asterisco supraíndice ( * ).

Propiedades de Estrella o Clausura

Estrella de Kleene - Ejemplo 1 2

Intersección • La intersección de varios lenguajes regulares es otro lenguaje regular. Se utiliza la operación de intersección de conjuntos; así, para el alfabeto Σ ={x,y} si L1 = {x,xy,yy}, L2 = {yz,yy} y L3 = {y,yy} entonces su intersección será L1 Ç L2 ÇL3 = {yy}. • Para ejemplificar la intersección, utilizaremos un modelo distinto.

Propiedades de Intersección

Intersección - Ejemplo • Para diseñar el autómata finito que admite el lenguaje intersección aplicamos: • S' será el producto cartesiano de todos los conjuntos de estados originales S' = S1 x S2 x S3 x...x Sn. • En nuestro caso particular, S1 = { 1, ,2 } y S2 = { 3, 4 } el producto cartesiano s' = S1 | x| S2 = { (1,3), (1,4), (2,3), (2,4) }. • El alfabeto tiene que ser el mismo para todos los autómatas. S' = S = { x, y }. • El estado inicial será aquel que está formado por los estados iniciales originales: i' = ( i1, i2, i3,..., i n ). • En nuestro caso, es el par (1,3). • Los estados de aceptación serán aquellos que están formados por estados de aceptación originales. F' = (F1,F2,F3,..., Fn). • En nuestro caso solo tenemos un estado de aceptación en f', que es el par (2,3)

Intersección - Ejemplo

Propiedades de Complemento y Diferencia

Referencias • http://www.aconute.es/computacion/automa tasFinitos/ejemplo_opers.html • https://automaton.wikispaces.com/2.3.+Defin ición+formal+de+autómatas+finitos • http://www.aconute.es/computacion/automa tasFinitos/ta_cap1_6.html • http://www.virtual.unal.edu.co/cursos/cienci as/2001018/lecciones/PDFs/Cap1/Cap1b.pdf • http://trevinca.ei.uvigo.es/~formella/doc/tal f05/talf/node38.html

Add a comment

Related presentations

Related pages

Lenguajes formales | Automátas, gramáticas y lenguajes ...

Lenguajes formales En esta página vamos a explicar que son, como se utilizar y cuales son las funciones de los lenguajes formales: Introducción: Definiciones
Read more

Automatas | Automátas, gramáticas y lenguajes formales

Resúmenes y apuntes de autómatas finitos deterministas y no ... ya que aparte de la utilización de los lenguajes formales en los autómatas finitos, ...
Read more

Amazon.com: Lenguajes formales y autómatas (Spanish ...

La presente obra trata acerca de la definición de lenguajes formales mediante procesos que especifiquen su estructura de una manera precisa con ayuda de ...
Read more

Teoría de Autómatas y Lenguajes Formales – Page 2 – La ...

Enunciado practica 5. Autómatas finitos no deterministas. 1.- Dado el autómata finito no determinista descrito por la siguiente tabla, obtener el ...
Read more

Cursos de Informática: Lenguajes Automatas

... de lenguajes formales y autómatas. ... lenguajes formales como autómatas finitos no deterministas, pushdown autómatas no deterministas, ...
Read more

Autómatas Finitos: RECONOCEDOR DE LENGUAJE

... de un autómata que reconoce lenguajes formados ... lenguajes formales y autómatas finitos deterministas ... DE LOS AUTÓMATAS FINITOS ...
Read more

Autómatas finitos no determinista: Punto de vista informal ...

Teoría de Autómatas y Lenguajes Formales. 1era cohorte ... se tienen en cuenta que existen autómatas finitos deterministas y los no deterministas ...
Read more

Teoría Automátas Lenguajes Formales.pdf - scribd.com

Teoría de Autómatas y Lenguajes Formales al desarrollo de ... especial lo relacionado con expresiones regulares y con autómatas finitos deterministas.
Read more

Autómata finito determinista - Wikipedia, la enciclopedia ...

Ejemplo de AFD con dos estados. En nodo de la izquierda es inicial y de aceptación. Un autómata finito determinista (abreviado AFD) ...
Read more