# data[].attributes.attachment_caption
Representación Gráfica de un árbol de derivación.

# data[].attributes.headline
Árboles de derivación (Emil Moquete 22-0969)

# data[].attributes.subject
Árboles de derivación (Emil Moquete 22-0969)

# data[].attributes.body
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 conjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:

Hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.

Todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por encima del nodo.

Todos los nodos están conectados al nodo raíz mediante un único camino.

Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores.

Propiedades de un árbol de derivación.

Sea G = (N,T,S,P) una gramática libre de contexto, sea A ∈ N una variable. Diremos que un árbol TA = (N,E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes:

La raíz del árbol es un símbolo no terminal.

Cada hoja corresponde a un símbolo terminal o λ.

Cada nodo interior corresponde a un símbolo no terminal.

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.

Referencias:

Alejandra, M. (s. f.). Arboles de derivaciòn. https://teodelacomp.blogspot.com/2011/03/arboles-de-derivacion.html

Traductores e Intérpretes UCAB : Arboles de Derivacion. (s. f.). http://www.suigeneris.org/UCABTI/Arboles%20de%20Derivacion.html

# data[].attributes.attachment_caption
Arbol de derivación: Sea G=(N,T,S,P) una GLC con P: S→ ab|aSb. La derivación de la cadena aaabbb será: S ⇒ aSb ⇒ aaSbb ⇒aaabbb.

# data[].attributes.headline
Árboles de derivación - Parte 2 (Emil Moquete 22-0969) 

# data[].attributes.subject
Árboles de derivación - Parte 2 (Emil Moquete 22-0969) 

# data[].attributes.body
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.

Si un nodo está etiquetado con una variable X y sus descendientes (leídos de izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X → X1…Xk en G.

Sea G=(N,T,S,P) una GLC. Un árbol es un árbol de derivación para G si:

1. Todo vértice tiene una etiqueta tomada de T ∪ N ∪ (λ).

2. La etiqueta de la raíz es el símbolo inicial S.

3. Los vértices interiores tienen etiquetas de N.

4. Si un nodo n tiene etiqueta A y n₁n₂...nk respectivamente son hijos del vértice n, ordenados de izquierda a derecha, con etiquetas x₁,x₂..xk respectivamente, entonces: A→ x₁x₂...xk debe ser una producción en P.

5. Si el vértice n tiene etiqueta λ, entonces n es una hoja y es el único hijo de su padre.

# data[].attributes.body
Las Gramáticas de Contexto Libre (GCL) son un tipo de gramática formal que se utiliza para definir la estructura de lenguajes formales, como los lenguajes de programación y los lenguajes naturales. En una GCL, las reglas de producción se aplican independientemente del contexto en el que aparezcan, lo que facilita su uso en el análisis sintáctico.

Componentes Principales

Símbolos Terminales: Son los elementos básicos del lenguaje, es decir, los caracteres o tokens finales que no se pueden descomponer más. Ejemplos incluyen palabras clave o caracteres individuales en lenguajes de programación.

Símbolos No Terminales: Son los elementos abstractos que se pueden descomponer o reemplazar mediante reglas de producción. Representan estructuras como expresiones o sentencias.

Símbolo Inicial: Es el punto de partida de la derivación de una cadena en el lenguaje. Normalmente se denota por un símbolo no terminal, desde el cual se empiezan a aplicar las reglas de la gramática.

Reglas de Producción: Son las reglas que permiten transformar un símbolo no terminal en una secuencia de símbolos terminales y no terminales. Se expresan en la forma A → α, donde A es un símbolo no terminal y α es una cadena de símbolos que puede incluir terminales y no terminales.

Ejemplo:

Considera la siguiente gramática que genera cadenas de paréntesis balanceados:

Símbolos Terminales: (, )

Símbolos No Terminales: S

Símbolo Inicial: S

Reglas de Producción:

S → (S)S

S → ε (ε representa la cadena vacía)

Referencias:

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Addison-Wesley.

Massachusetts Institute of Technology (MIT). (n.d.). Theory of computation [Lecture notes]. MIT OpenCourseWare. https://ocw.mit.edu

# data[].attributes.attachment_link.title
Lenguajes y Autómatas - Módulo 2.1 (Gramáticas libres de contexto)

# data[].attributes.attachment_caption
Las tres principales reglas de la forma normal de Chomsky

# data[].attributes.headline
Forma Normal de Chomsky (Jean Roque 23-0812)

# data[].attributes.subject
Forma Normal de Chomsky (Jean Roque 23-0812)

# data[].attributes.body
Una gramática libre de contexto se dice que está en forma Normal Chomsky si sigue las siguientes reglas de producción:

A → BC

A → a

S → ε

Aquí, A, B y C son símbolos no terminales, la letra "a" es un símbolo terminal y S es la cadena inicial, la cuál deriva a la cadena vacía ε. En este contexto, B y C no pueden ser los símbolos iniciales y la tercera regla solo puede aparecer si ε pertenece al lenguaje producido por esta gramática. Para transformar una GLC para que esté en forma normal Chomsky, se siguen una serie de transformaciones simples en un determinado orden:

1) Inicio: Eliminar el símbolo de inicio de los lados derechos

Se introduce un nuevo símbolo de inicio S₀, y la regla S₀ → S₁, donde S₁ es el símbolo de inicio anterior. El lenguaje no cambia y S₀ no aparecerá en el lado derecho de ninguna otra regla.

2) Término: Eliminar reglas con terminales no solitarios

Para eliminar cada regla con terminales no solitarios (A → X ₁... a... Xn), se crea un símbolo terminal Na, y la nueva regla Na → a, y se cambia la regla a A → X ₁... Na... Xn. Si aparecen varios símbolos terminales en el lado derecho, se reemplaza al mismo tiempo todos ellos por su símbolo no terminal asociado.

3) BIN: Elimina los lados derechos con más de 2 no terminales

Se reemplaza con más de 2 no terminales por reglas A → X ₁ X ₂... Xn con más de 2 no terminales X ₁, X 2, ...,Xn por reglas:

A → X ₁ A ₁,

A ₁ → X ₂ A ₂,

...

An₋₂ → Xn₋₁ Xn,

, donde Ai son nuevos símbolos no terminales.

4) DEL: eliminar las reglas ε

Para eliminar esta regla A → ε, donde A no es S₀, se debe de primero de encontrar el conjunto de todos los no terminales que derivan de ε. Estos tipos de símbolos se les llama anulables y se calculan de la siguiente manera:

Si existe la regla A → ε, entonces A es nulo

Si la regla A → X ₁... Xn existe, y cada Xi es nula, entonces A también es nulo

Se reemplaza cada regla por todas las versiones con alguna Xi anulable omitida. Cuando se eliminan cada regla ε, a menos que su lado izquierdo sea S0 se obtiene la gramática transformada.

5) UNIDAD: Eliminar reglas de unidad

Esta regla es de la forma A → B, donde A y B son no terminales. Para eliminarse, para cada regla B → X ₁... Xn donde X ₁... Xn es una cadena de no terminales y terminales, añadir regla A → X ₁... Xn, al menos que sea una regla de unidad que ya estaba eliminado.

Referencias:

Academia Lab. (2024). Forma normal de Chomsky. Enciclopedia. Revisado el 20 de septiembre del 2024. https://academia-lab.com/enciclopedia/forma-normal-de-chomsky/

Academy, E. (2023, 2 agosto). ¿Qué es la forma normal de Chomsky y cuáles son las restricciones específicas que impone a las gramáticas independientes del contexto? - Academia EITCA. EITCA Academy. https://es.eitca.org/cybersecurity/eitc-is-cctf-computational-complexity-theory-fundamentals/context-sensitive-languages/chomsky-normal-form/examination-review-chomsky-normal-form/what-is-chomsky-normal-form-and-what-are-the-specific-constraints-it-imposes-on-context-free-grammars/

# data[].attributes.headline
Proceso de construcción de un autómata a partir de una gramática (Angel Garcia 23-0599)

# data[].attributes.subject
Proceso de construcción de un autómata a partir de una gramática (Angel Garcia 23-0599)

# data[].attributes.body
Para construir un autómata a partir de una gramática, el proceso varía según el tipo de gramática que estés trabajando. Los dos procesos mas comunes son gramáticas regulares y gramáticas libres de contexto.

1. Gramática Regular a Autómata Finito

Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del lenguaje. El autómata finito correspondiente será un autómata finito determinista (AFD) o no determinista (AFN).

Pasos:

Identificación de símbolos terminales y no terminales:

Los símbolos terminales (alfabeto) representan las transiciones del autómata.

Los símbolos no terminales (variables) se convierten en estados del autómata.

Creación de transiciones:

Para cada regla de producción de la forma A → aB (donde A y B son no terminales, y a es un terminal), dibujas una transición desde el estado A al estado B con la etiqueta a.

Si tienes una regla A → a (sin un no terminal), dibujas una transición desde el estado A a un estado de aceptación (estado final) con la etiqueta a.

Define el estado inicial y los estados de aceptación:

El estado inicial del autómata es el símbolo inicial de la gramática.

Los estados de aceptación son aquellos donde las producciones no tienen más no terminales (es decir, derivan solo en terminales).

Ejemplos:

S → aA

A → a

A → bS

Referencias:

Juancar Molinero. (2014, 16 febrero). Definición formal de un autómata finito determinista (AFD) [Vídeo]. YouTube. https://www.youtube.com/watch?v=P0AxQvJcN2Q

https://users.exa.unicen.edu.ar/catedras/ccomp1/ApunteGRyER.pdf

# data[].attributes.attachment_link.title
Definición Formal de un Autómata Finito Determinista (AFD)

# data[].attributes.headline
Proceso de construcción de un autómata a partir de una gramática - parte 2 (Angel Garcia 23-0599)

# data[].attributes.subject
Proceso de construcción de un autómata a partir de una gramática - parte 2 (Angel Garcia 23-0599)

# data[].attributes.body
2. Construcción de un Autómata de Pila a partir de una Gramática Libre de Contexto

Una gramática libre de contexto es más compleja que una regular y genera lenguajes libres de contexto. El autómata que representa estas gramáticas es un autómata de pila. Este tipo de autómata usa una pila para manejar las derivaciones, que pueden involucrar múltiples símbolos.

Pasos:

Identifica las reglas de la gramática:

Cada producción de la forma A → a (donde A es un no terminal y a es una combinación de terminales y no terminales) servirá como base para las transiciones en el autómata.

Configura la pila:

Los no terminales se apilan en la pila y son reemplazados por sus producciones según las reglas de la gramática.

A medida que el autómata procesa los terminales, se asegura de que las entradas coincidan con lo que está en la pila.

Definir estados y transiciones:

El autómata tiene un estado inicial y un estado de aceptación.

Las transiciones implican manipular la pila (apilar y desapilar) para aplicar las producciones de la gramática.

Ejemplo:

S → aSb

S → s

Referencias:

Juancar Molinero. (2012, 14 mayo). De Gramática Independiente del Contexto a Autómata a Pila [Vídeo]. YouTube. https://www.youtube.com/watch?v=Q_b4c5kmV1Q

https://ocw.unican.es/pluginfile.php/2451/course/section/2492/3-8_CFL.pdf

# data[].attributes.attachment_link.title
De Gramática Independiente del Contexto a Autómata a Pila