Wikipedia

Resultados de la búsqueda

viernes, 25 de agosto de 2017

TIPOS DE GRAMATICA




Ø TIPO “0” O “No restringida o recursivamente enumerables”: 

     Incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes de ser reconocidos por una maquina de TuringY con este lenguaje se hacen los parser de un compilador
     
    CARACTERÍSTICAS: De este tipo es que del lado derecho de cada producción puede empezar con un símbolo terminal o con un no terminal y del lado izquierdo puedes empezar con más de un símbolo no terminal.

    
    RESTRICCIONES: Es que no tiene solamente que el del lado izquierdo debe haber por lo menos un símbolo no terminal  

NOTA: “+” significa “sin incluir la cadena vacía” y significa “incluyendo la cadena vacía”. “I” significa “o”.

Estos lenguajes también son denominados “recursivamente enumerables”


Ø TIPO “1” O “Sensible al contexto”:

Estos tipos de lenguajes se resuelven mediante autómatas lineales limitados. Con este tipo se hacen los parser (analizador sintáctico) de un compilador que transforma su entrada en un árbol de derivación.
El analizador sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada

CARACTERÍSTICAS: Del lado derecho de cada producción puede empezar con un símbolo terminal o con un no terminal y del lado izquierdo puede empezar con más de un símbolo no terminal.

RESTRICCIONES: el número de no terminales del lado izquierdo de la producción debe ser menor o igual al número de símbolos del lado derecho


NOTA: Los lenguajes regulares y los libres de contexto también se puede resolver mediante autómatas lineales limitados

Ø TIPO “2” O “Libres o Independientes de contexto”:

Estos tipos de lenguajes se resuelven mediante autómatas descendentes y con este tipo de lenguaje se programa los parser en un compilador, permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de los lenguajes de programación está definida mediante gramáticas libres de contexto.

CARACTERISTICAS: Del lado derecho de cada producción puede empezar con símbolo terminal o con un no terminal

Los lenguajes regulares también se pueden resolver mediante autómatas descendentes  

Ø TIPO “3” O “Lenguajes regulares”:

Estos tipos de lenguajes se resuelven mediante autómatas finitos y con este tipo de lenguaje se hacen los scanners. Estas gramaticas se restrigen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal y también esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares

CARACTERÍSTICAS: Del lado derecho de cada producción debe empezar con un símbolo terminal.

Aquí le dejo una tabla donde se representan los tipos de lenguaje según sus características.


DEFINICION ALFABETOS, CADENA, LENGUAJE, TIPOS DE LENGUAJE, GRAMÁTICA Y AUTÓMATAS



ALFABETO

Un alfabeto es un conjunto de símbolos finito y no vacío de elementos llamados símbolos o letras. Es una agrupación, que se lee con un orden determinado, de las gráficas utilizadas para representar el lenguaje que sire de sistema de comunicación, un grupo de letras estructurado bajo un orden especifico aceptado a nivel general en el marco de una lengua
Convencionalmente, utilizados el símbolo ∑ (sumatoria) para designar un alfabeto. Entre los alfabetos más comunes se incluyen los siguientes:

Ø ∑= {0,1}, el alfabeto binario

Ø ∑= {a, b, ……. z}, es el conjunto de todas las letras minúsculas

Ø El conjunto de todos los caracteres ASCII

 cadena

Una cadena de caracteres (que también se denomina en ocasiones palabra) es una secuencia finita de símbolos seleccionados de algún alfabeto.
Una cadena o palabra es una secuencia finita de símbolos que pertenecen a un alfabeto y comúnmente se denota con la letra.

Ø EJEMPLO: si ∑= {0,1}, entonces ∑1= {0,1}, ∑2= {00, 01, 10, 11}, ∑3= {000, 001, 010, 011, 100, 101, 110, 111}, etc.

LA CADENA VACÍA

La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena, designada por £, es una cadena que puede construirse en cualquier alfabeto

Ø EJEMPLO: observe que ∑0= {£}, independientemente de cuál sea el alfabeto ∑. Es decir, £ es la única cadena cuya longitud es 0.

  Lenguajes

Un conjunto de cadenas, todas ellas seleccionadas de un ∑*, donde ∑ es un determinado alfabeto se denomina lenguaje. Ya que estas pueden ser cualquier cadena que cumpla con lo siguiente, está formada por los símbolos. Los lenguajes habituales pueden interpretarse como conjuntos de cadenas.

Ø EJEMPLO: Seria el inglés, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras.

Ø EJEMPLO: Es el lenguaje C, o cualquier otro lenguaje de programación, donde los programas correctos son un subconjunto de las posibles cadenas que pueden formarse a partir del alfabeto del lenguaje.

  Tipos de Lenguajes

Ø LENGUAJES DECLARATIVOS: Es fundamentalmente lenguajes de órdenes, dominados por Sentencias que expresan “lo que hay que hacer” en vez de “cómo hacerlo”.

Ø LENGUAJES DE ALTO NIVEL: Son los más utilizados como lenguajes de programación permiten que los algoritmos se expresen en un nivel y estilo de escritura fácilmente legible y comprensible por otros programadores.

Ø LENGUAJE ENSAMBLADOR: Es el programa en que se realiza la tracción de un programa escrito en un programa escrito en ensamblador y lo pasa a lenguaje máquina. Directa o no directa de la traducción en que las instrucciones no son más que instrucciones que ejecuta la computadora.

Ø LENGUAJE MAQUINA: Es como la maquina interpreta lo que nosotros queremos hacer es una lectura de 0 y 1 es decir binario.

 Gramática

La gramática es un ente formal para especificar, de una manera finita, el conjunto de cadenas de símbolos que constituyen un lenguaje.
Es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecidas a un lenguaje especifico y dos gramáticas que describen el mismo lenguaje que llaman gramáticas equivalentes.
  
Autómata

Un autómata es una construcción lógica que recibe una entrada y produce una salida en función de todo lo recibido hasta ese instante. En el caso de los Procesadores de Lenguaje un autómata es una construcción si dicha cadena pertenece o no a un determinado lenguaje.