Modelo económico

Capítulo 1 Conceptos Básicos

Este capítulo presenta una visión global de la teoría de los lenguajes. Primero se dan las definiciones básicas. Luego se describen los conceptos de sintaxis y semántica. Estos conceptos serán cubiertos en más profundidad en los capítulos siguientes.

1.1 Definiciones

En esta sección se presentan las definiciones básicas de la teoría de lenguajes. Estas definiciones son necesarias para el resto del libro1. El lector notará la analogía entre la teoría de cadenas y la teoría de secuencias vista en [Gries94]. Comenzamos con los elementos constructores de los lenguajes. El elemento más sencillo es el alfabeto:

Definición 1.1. Un alfabeto es un conjunto finito de símbolos.

De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está haciendo referencia a un solo carácter. Los símbolos se pueden denotar con nombres. Los siguientes son ejemplos de alfabetos: {a,b,c} {while, if, else, +,++, {,}, -, =, class, extends, private, public} {sustantivo, verbo, pronombre, adjetivo, adverbio, preposición} {1, 2, ..., n}

El siguiente concepto de la teoría de lenguajes es el de cadena o palabra (o programa!). Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto. Por ejemplo, dado el alfabeto {a, b, c} podemos formar las siguientes palabras o cadenas: a, b, ab, cab, bb, aaaa.

Definición 1.2. Dado un alfabeto A, una cadena sobre A es una sucesión de longitud finita (mayor o igual a cero) de símbolos del alfabeto. La letra griega lambda, , se usa para denotar la cadena vacía sobre cualquier alfabeto.

...