Jerarquia De Chomsky

Introducción

En el campo de la informática, el concepto de Gramática Formal adquirió gran importancia para el desarrollo de lenguajes de programación, consiguientemente el desarrollo de autómatas y máquinas de Turing cobró vida en las últimas décadas, fortaleciendo el vínculo entre Electrónica e Informática, creando máquinas cada vez más sofisticadas y menos complicadas para el usuario final.

En este informe se darán a conocer los tipos de gramáticas según la jerarquía de Chomsky en función de la forma de reglas de derivación o producción, además de mostrar ejemplos en cada una de ellas.

Jerarquía de Chomsky

En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.

Chomsky definió cuatro tipos distintos de gramáticas en función de la forma de las reglas de derivación.

La clasificación comienza con un tipo de gramáticas que pretende ser universal, y aplicando restricciones a sus reglas de derivación se van obteniendo los otros tres tipos de gramáticas.

La jerarquía de gramáticas se clasifica en cuatro tipos: 0, 1, 2, y 3, donde la más general es la 0, y conforme avanza el número que las identifica, aumentan las restricciones. Las gramáticas de tipo 0, contienen a todas las demás. Las de tipo 1 contienen a las de tipo 2, y por último las de tipo 2 contienen a las de tipo 3. Por lo tanto se define una jerarquía de gramáticas respecto de la relación de inclusión.

Expresiones Regulares.

Una expresión regular, a menudo llamada también patrón, es una expresión que describe un conjunto de cadenas sin enumerar sus elementos

Para poder realizar expresiones regulares debemos tomar en cuenta esto:

Sea S y R símbolos cualesquiera:

1. entonces R y/o S son expresiones regulares

2. R*S=RS es una expresión regular

3. (R) es una expresión regular

4. nulo (vacío) es una expresión regular

5. R*=a que R puede repetirse 0 muchas veces

6. R+=R(R*) R se repite 1 o más veces

7. R?=R o vacío quiere decir que R puede venir 1 vez o no venir nunca

Ejemplos:

Supongamos que se desea generar una expresión regular que reconozca un código de pasaporte:

La solución seria

Formato de no. Pasaporte=A1-12354544

Expresión regular que reconoce éste tipo de información

LD-DD*

Donde

L representa al conjunto de todas las letras del alfabeto

D representa el conjunto de todos los decimales

Supongamos que se desea generar una expresión regular que reconozca números decimales.

DD*.DD*

Aquí decimos que puede venir un digito (D) seguido de otro digito que puede venir 0 o muchas veces (D*) hágase notar que el (.) que se encuentra no es de concatenación sino que es el punto decimal, después de esto viene otro digito (D) obligatorio ya que no se acepta 3. ya que no sería un número decimal.

Gramática tipo 3 Lenguajes Regulares.

Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades: Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.

Puede ser reconocido por:

un autómata finito determinista

un autómata finito no determinista

un autómata de pila

un autómata finito alterno

una máquina de Turing de solo lectura

Es generado por:

una gramática regular

una gramática de prefijos

Es

...