Jerarquía de chomsky

Reglas de un lenguaje que Permiten asignar a las distintas partes de un programa y verificar su Corrección.

Formado por las definiciones y Reglas que permiten comprobar el dominio de un identificador, y en qué Contextos puede ser usado.

Cada lenguaje tiene un sistema de Tipos propio, aunque puede variar de una a otra implementación.

La comprobación de tipos es parte Del análisis semántico.

*Inferencia de tipos

Calcular y mantener la información sobre los tipos de datos.

Verificación de tipo

Asegurar que las partes de un programa tienen sentido según las reglas de tipo Del lenguaje.

*Tipos simples

Son Expresiones de tipos los tipos simples del lenguaje, y algunos tipos Especiales:

Integer, real, char, boolean, Void, error.

*Constructores de tipos

Permiten Formar tipos complejos a partir de otros más simples. La semántica de cada Lenguaje tiene asociada unos constructores de tipos propios. En general, en los Lenguajes de programación se definen los siguientes constructores:

Un comprobador de Tipos verifica que el uso de los objetos en los constructos de uso se Atiene a lo especificado en sus declaraciones o definiciones de acuerdo a las Reglas especificadas por el sistema de tipos.

*Estático

Su comprobación De tipos ocurre en tiempo de compilación sin tener que comprobar equivalencias En tiempo de ejecución.

*Dinámico

El lenguaje Realiza comprobaciones de tipo en tiempo de ejecución. 

Conversión implícita

: No se requiere una sintaxis especial porque la Conversión se realiza con seguridad de tipos y no se perderán datos. Puede Realizarse una conversión implícita cuando el valor que se va a almacenar puede Ajustarse a la variable sin necesidad de redondeo.

Conversión explícita

:Una conversión de Tipo es una manera de informar al compilador de forma explícita de que pretende Realizar la conversión y que está al tanto de que puede producirse una pérdida De datos debido a que el tipo de la Variable de destino es más pequeño que la variable de origen.

Una conversión de tipo (casting) El casting o cast permite hacer una conversión explícita de Un tipo de dato a otro, a criterio del programador siempre y cuando estos tipos Sean compatibles

Red de cocientes de un autómata Finito

Una red de cocientes de un Autómata finito esta conformado por la expresión: A=(Q,∑ , δ, I, F).                     

El conjunto de autómatas Cocientes de A esta ordenado por la relación, A/π1donde A/π2 si y sólo si Existe una partición π del conjunto de estados A/π1 tal que (A/π1)/π = A/π2; Esto es, si A/π2 es un autómata cociente de A/π1.

Lo expresión anterior de defino Como: 

Q = Es el conjunto de estados

∑ = Es el alfabeto de entrada

Δ = Función de transición

I = Estado inicial

F = Conjunto de estado final

Un ejemplo de lo explicado es; el Conjunto que A=({0,1,2}, {α}, δ, {0}, {2}).

Un lenguaje finito “L” tiene una Estructura más compleja que el autómata “A”. 

Si L C L(A) y existe una Aceptación de “L” por el autómata “A”, y se utiliza una transición de “A”. Se Ocupa cada estado I como estado inicial y el estado F como estado final.

Puede parecer que todos los Autómatas finitos existen un lenguaje finito estructuralmente completo respecto A él.

Hay algunos autómatas finitos los Cuales no existe ningún lenguaje estructuralmente completo respecto a ellos.

En dos autómatas finito, por Ejemplo, A y A’ tales que L(A) ʌ L(A’)=0. 

Se le llama semired de cocientes Asociados a A y A’ al conjunto SemiLat(A,A’) formando por aquellos elementos A’’ de Lat(A)  tales que L(A’’) ʌ L(A’)=0. Y se llamara SemiLat(A,L) y será formado por aquellos elementos A’’ de Lat(A) tales que L(A’’) ʌ L=0.

Un ejemplo de lo anterior Es:  

En otro caso distinto, dados dos Autómatas distintos A y A’, llamaremos borde a la semired de cocientes Asociados a A y A’ al conjunto BS(A, A’) que esta formado por elementos de A’’ De SemiLat(A, A’) los cuales no existen en A’’’. 

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.

La Jerarquía de Chomsky consta de Cuatro niveles:

• Gramática tipo 0

Gramáticas de tipo 0 (sin Restricciones), que incluye a todas las gramáticas formales. Estas gramáticas Generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables.

Jerarquía De Chomsky La Jerarquía (Gramática Tipo 1)

Gramáticas de tipo 1 (gramáticas Sensibles al contexto) generan los lenguajes sensibles al contexto. Estas Gramáticas tienen reglas de la forma αAβ→αAγβ con A un no terminal y α,β,γ, Cadenas de terminales y no terminales. Las cadenas α y β pueden ser vacías pero γ no puede serlo.

• Gramáticas de tipo 2

Gramáticas de tipo 2 (gramáticas Libres del contexto) generan los lenguajes independientes del contexto. Las Reglas son de la forma A→ γ con A un no terminal y γ, una cadena de terminales Y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos por un Autómata con pila.