Matematicas para la computacion Introduccion de lenguajes formales y automatas Tarea 29 de noviembre 2014





Matemáticas para la computación

Introducción de lenguajes formales y autómatas

David Martínez Ayala

SCO1SB111




Índice

Introducción............................................................................1
Gramática y lenguaje formal....................................................1
Gramática libre de contexto.....................................................1
Autómatasfinitos....................................................................2
Autómata finito determinista...................................................2
Autómata finito no determinista..............................................3
Máquina de Turing...................................................................3Bibliografía..............................................................................6























Introducción
Un lenguaje formal, es un lenguaje descrito mediante un formalismo matemático.
Desde su nacimiento, la teoría de autómatas ha encontrado aplicación en muy diversos campos. Se debe a que resulta muy natural considerar, tanto los autómatas como las máquinas secuenciales, sistemas capaces de transimitir (procesar) información. Esto es equiparable acualquier sistema existente en la naturaleza, que recibe señales de su entorno, reacciona ante ellas y emite nuevas señales al ambiente que le rodea.

Gramática y lenguaje formal
En la teoría del lenguaje formal, una gramática es un conjunto de reglas de produción para cadenas en un lenguaje formal. Estas describen cómo formar cadenas del alfabeto de la lengua que son válidos de acuerdo a la sintaxis dellenguaje.

Una gramática formal es una estructura matemática con un conjunto de reglas de formación que definen las cadenas de caracteres admisibles en un determinado lenguaje formal o lengua natural. En un lenguaje formal, a las cadenas foradas según las reglas de la gramática formal se les llama fórmulas bien formadas, y el conjunto de todas las fórmulas bien formadas constituye un lenguajeformal.

Gramática libre de contexto
Una gramática libre de contexto (GLC) es una tupula con cuatro parámetros:

G=(V, T, P, S)

V – conjunto de símbolos variables
T – conjunto de símbolos terminales
S ∈ V, símbolo inicial
P – conjunto de reglas de producción:
A -> α, con α sucesión de símbolos de V ∪ T, eventualmente vacía (α = ε)


Autómatas finitos
Un autómata finito es un conjunto de estados y uncontrol que se mueve de un estado a otro en respuesta a entradas externas.
Los autómatas finitos se pueden clasificar en función de tipo de control como:
Deterministas. El autómata únicamente puede estar en un estado en un momento determinado.
No deterministas. El autómata puede estar en varios estados simultáneamente.
Ambos definen los mismos lenguajes (regulares), sin embargo los Nodeterministas permiten describir más eficientemente determinados problemas.

Autómata finito determinista
El término «determinista» hace
referencia al hecho de que para cada entrada sólo existe uno y sólo un
estado al que el autómata puede hacer la transición a partir de su
estado actual.Autómatas Finitos Deterministas (2)
El término «Autómata Finito» hace referencia a la variedad
determinista, aunquenormalmente utilizaremos el término
«determinista», o la abreviatura AFD, con el fin de recordar el tipo de
autómata del que estamos hablando.Definición de Autómata Finito Determinista
Un Autómata Finito Determinista consta de:
1.Un conjunto finito de estados, a menudo designado como Q.
2.Un conjunto finito de símbolos de entrada, a menudo designado como
∑ (sigma).
3.Una función de transición que tomacomo argumentos un estado y un
símbolo de entrada y devuelve un estado. La función de transición se
designa habitualmente como ᵟ o Δ (delta).
4.Un estado inicial, uno de los estados de Q.
5.Un conjunto de estados finales o de aceptación F. El conjunto F es un
subconjunto de Q.


Autómata finito no determinista
Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a...