GRAMATICAS LIBRES DE CONTEXTO
Las gramáticas libres de contexto amplían la capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito. Las gramáticas libres de contexto son útiles para describir expresiones aritméticas que tengan una anidación arbitraria de paréntesis balanceados y estructuras de bloque en los lenguajes de programación.ARBOLES DE
DERIVACIÓN
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje. Un árbol es un grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamado nodo raíz, mediante un único camino. Un nodo n1 se dice descendiente de otro nodo n2 si sepuede llegar a n1 a partir de n2. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientes se denominan hojas. El resto de los nodos sedenominan nodos interiores. Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) unárbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena. FORMAS
NORMALESDE CHOMSKY
Proposición 3.1 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contexto G’=(V’,T,P’,S’) en forma normal de Chomsky. En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G” sin variables inútiles ni producciones vacías ni produccionesunitarias equivalente a G. A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma , con y , la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción . Así pues las producciones que no sean de la forma con Xvariable y a terminal, han de ser de la forma , con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e incorporamos la sucesión de producciones
ELIMINACION DE FACTORES COMUNES IZQUIERDOS
Un automata finito o maquina de estado finito es un modelo matematico de un sistema que recibe una cadena constituida por simbolos de un alfabeto y determina si esacadena pertenece al lenguaje que el autamata reconoce. Definicion formal Formalmente, un autoata finito (AF) puede ser descrito como una 5-tupla (S,W,T,s,A) donde: W es un alfabeto; S un conjunto de estados; T es la funcion de transicion: ; es el estado inicial; es un conjunto de estados de aceptacion o finales. Ejemplo 1 w= {0,1}, S = {S1, S2}, T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})} s= S1 A = {S1}. Formas de representar un automata finito Ademas de notar un AF a traves de su definicion formal es posible representarlo a traves de otras notaciones que resultan mas comodas.
AUTOMATAS PUSH-DOWN
Un autómata de pila o Push-Down es un autómata que cuenta con un mecanismo que permita almacenamiento ilimitado y opera como una pila. El autómata de pila (se abrevia PDA de sus siglasen inglés Push-Down Autómata) tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto. El símbolo que se encuentra más a la izquierda se considera como que está en la “cima”. El dispositivo será no determinístico y tendrá un número finito de alternativas de movimiento en cada situación. MAQUINA DE TURING En 1936, Alan Turing contestó alentscheidungsproblem, la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. En el artículo On Computable Numbers, Turing construyó un modelo formal de computador, la Máquina de Turing, y demostró que había problemas tales que una máquina no…
