INTRODUCCIÓN A LA TEORÍA DE LENGUAJES FORMALES.

Lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados.

Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial con los lenguajes naturales.

En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante , o .

1.1 Alfabeto: Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje y al conjunto de las reglas se lo llama la gramática formal (o sintaxis).

1.2 Cadenas: A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada (o palabra) del lenguaje.

1.3 Lenguajes: Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de símbolos primitivos

Ej: El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos

0, 1, 2, 3, 4, 5, 6, 7, 8 y 9

1.4 Tipos de lenguajes: Chomsky clasificó jerárquicamente las gramáticas formales que generan lenguajes formales, en estos tipos:

• Tipo 3: Gramáticas regulares que generan lenguajes regulares

• Tipo 2: Gramáticas incontextuales que generan lenguajes incontextuales

• Tipo 1: Gramáticas contextuales que generan lenguajes contextuales

• Tipo 0: Gramáticas libres que generan lenguajes sin ningún tipo de restricción

Cuanto menor es el tipo, mayor es el poder expresivo del lenguaje generado y más complejidad tiene su tratamiento por parte de una máquina.

...