Gramaticas Y Lenguajes Formales

Gramaticas Y Lenguajes Formales

GRAMATICA

Esta Pagina sera modificada por Brenda Maria Salazar Chavez//

La gramática de un lenguaje es el conjunto de reglas capaces de generar todas las posibilidades combinatorias de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.

La expresión “gramática formal” tiene dos sentidos:

(a) gramática de un lenguaje formal. (b) descripción formal de la gramática de un lenguaje natural.

En cuanto a (b), la descripción formal de la gramática de una lengua es la que explicita las reglas combinatorias mentales a partir de fórmulas lógico-matemáticas.

Estas reglas combinatorias que utiliza el lenguaje natural reciben el nombre de sintaxis, y son inconscientes.

En cuanto a (a), ‘gramática formal’ se utiliza en analogía con el concepto de gramática, usado tradicionalmente para los lenguajes naturales. Por tanto, una gramática formal es el conjunto de reglas combinatorias de un lenguaje formal. Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la Jerarquía de Chomsky).

Imaginemos una gramática con estas dos reglas:

1. A → bAc 2. A → de

La idea es substituir el símbolo inicial de la izquierda por otros símbolos aplicando las reglas. El lenguaje al cual representa esta gramática es el conjunto de cadenas de símbolos que pueden ser generados de esta manera: en este caso, por ejemplo:

 A → bAc → bbAcc → bbbAccc -→ bbbdeccc.

El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son símbolos terminales. Las cadenas de la lengua son aquellas que solo contienen elementos terminales, como por ejemplo: bbbdeccc, de, bdec, … Estas serían tres posibles realizaciones del lenguaje cuya gramática hemos definido con dos reglas.

LENGUAJE FORMAL

En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.

Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, en derecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal, en el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir métodos computacionales. Sin embargo, hoy en día, el punto de vista de que la naturaleza esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido informal antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes formales (en el sentido estricto de este artículo) gana cada vez más adeptos.

Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos a que b, por ejemplo.

La palabra vacía (esto es, la cadena de longitud cero) es permitida y frecuentemente denotada mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud también finita, un lenguaje puede bien incluir un número infinito de palabras.

Algunos ejemplos varios de lenguajes formales:

    * el conjunto de todas las palabras sobre {a, b}
    * el conjunto {an: n es un número primo}
    * el conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación
    * el conjunto de entradas para las cuales una particular máquina de Turing se detiene.

Los lenguajes formales pueden ser especificados en una amplia variedad de maneras, como:

    * cadenas producidas por una gramática formal (ver Jerarquía de Chomsky)
    * cadenas producidas por una expresión regular
    * cadenas aceptadas por un autómata, tal como una máquina de Turing

Varias operaciones pueden ser utilizadas para producir nuevos lenguajes a partir de otros dados. Supóngase que L1 y L2 son lenguajes sobre un alfabeto común. Entonces:

    * la concatenación L 1 L 2 consiste de todas aquellas palabras de la forma vw donde v es una palabra de L1 y w es una palabra de L2
    * la intersección L1&L2 consiste en todas aquellas palabras que están contenidas tanto en L1 como en L2
    * la unión L1|L2 consiste en todas aquellas palabras que están contenidas ya sea en L1 o en L2
    * el complemento ~L1 consiste en todas aquellas palabras producibles sobre el alfabeto de L1 que no están ya contenidas en L1
    * el cociente L1/L2 consiste de todas aquellas palabras v para las cuales existe una palabra w en L2 tales que vw se encuentra en L1
    * la estrella L1* consiste de todas aquellas palabras que pueden ser escritas de la forma W 1 W 2…Wn donde todo Wi se encuentra en L1 y n ≥ 0. (Nótese que esta definición incluye a ε en cualquier L*)
    * la intercalación L1*L2 consiste de todas aquellas palabras que pueden ser escritas de la forma v1w1v2w2…vnwn; son palabras tales que la concatenación v1…vn está en L1, y la concatenación w1…wn está en L2

Una pregunta que se hace típicamente sobre un determinado lenguaje formal L es cuán difícil es decidir si incluye o no una determinada palabra v. Este tema es del dominio de la teoría de la computabilidad y la teoría de la complejidad computacional.

Por contraposición al lenguaje propio de los seres vivos y en especial el lenguaje humano, considerados lenguajes naturales, se denomina lenguaje formal a los lenguajes «artificiales» propios de las matemáticas o la informática, los lenguajes artificiales son llamados lenguajes formales (incluyendo lenguajes de programación). Sin embargo, el lenguaje humano tiene una característica que no se encuentra en los lenguajes de programación: la diversidad.

En 1956, Noam Chomsky creó la Jerarquía de Chomsky para organizar los distintos tipos de lenguaje formal.


LEGUAJES FORMALES

Una manera formal de establecer un lenguaje es escribiendo las reglas que lo generan, de esta forma es mediante la definición de una gramática.

Definición. Una gramática es un cuarteto (V, ∑, p, S) donde:

I.V es un conjunto finito de símbolos no-terminales o variables.
II. ∑ es el alfabeto ó conjunto de símbolos terminales.
III. P es una relación en (V υ ∑)* son las reglas de producción tal que los primeros elementos en p contienen al menos un símbolo es V.
IV. S € V es el símbolo de comienzo.

De acuerdo a la forma de las reglas de producción se obtiene gramáticas de diferentes tipos. Las reglas de producción son las parejas en la relación y se utiliza E1→E2 para representar la regla (E1, E2) en p. La única condición que se le pide es que contenga por lo menos una variable en E1.

La longitud de una palabra es la cantidad de letras que la componen, así: E tiene longitud O, CASA tiene longitud 4, etc.

TIPOS DE GRAMATICAS
  • Gramática tipo 0. Cualquier gramática que cumpla con la definición.
  • Gramática tipo 1. En toda regla E1→ E2 la longitud de E1 es menor ó igual A la longitud E2
  • Gramática tipo 2. En toda regla E1→ E2, E1 € V.
  • Gramática tipo 3. En toda regla E1→ E2, E1 € V y E2 es un elemento de (∑*V υ ∑)
→PÉREZ CASTRO JOSÉ JONATHAN
→RAMIREZ CASILLAS MARIA DE LA CRUZ
→SANDOVAL CASTORENA SIVEL KARINA
→VILLA VERGARA JOHANNA LIZETTE

Equipo 2

1-B informatica a qui empieza nuestro trabajo 6.2
maestro: Alberto Lomeli.
integrantes:

             Mata Leon Juan Carlos
             Acevedo Estrada Juan Antonio
             Gonzales Tafolla Demetrio de Jesus
             Ortega Romero Christian 

Gramatica y Lenguajes Formales:

Gramatica:

Una gramática es un conjunto de reglas que sigue un lenguaje para la estructura de palabras válidas. Las gramáticas por lo regular producen cadenas o palabras que pertenecen a algún lenguaje, y la producción de estas palabras está determinada por reglas de sustitución bien definidas. A estas reglas también se les llama producciones. Dicho lo anterior, podemos decir que un lenguaje es descrito por una gramática , donde es una túpla de cuatro elementos , donde:

. Un conjunto de símbolos no terminales, que funcionan como variables a través de las reglas de producción. Son substituidas, en cada paso, por una secuencia de símbolos que pueden ser terminales, no terminales o una combinación de ambos.

. Es el símbolo inicial del cual derivan las demás producciones por medio de las reglas de producción.

. Un alfabeto sobre el cual se generará el lenguaje. A los símbolos de este alfabeto se les llama terminales, ya que una vez que forman parte de la palabra producida, no son reemplazados por algún otro símbolo.

. Es el conjunto de reglas de producción, con el cual se generarán las posibles cadenas que integren el lenguaje.

Podemos pensar en las gramáticas como las reglas que estructuran el lenguaje. Es común que se utilicen letras mayúsculas para denotar a los símbolos no terminales y letras minusculas para denotar a los símbolos terminales. El lenguaje generado por una gramática comunmente se denota como .


Tipos de gramática

Entre los principales tipos de gramática o enfoques en el estudio de la gramática se encuentran:

La gramática prescriptiva, o gramática normativa es la que presenta autoritariamente normas de uso para un lenguaje específico, tendiendo a despreciar las construcciones no estandarizadas. La gramática tradicional es típicamente prescriptiva. Este tipo de gramática está basada usualmente en el dialecto de prestigio de una comunidad hablante, y condena a menudo ciertas construcciones que son comunes entre los grupos socioeconómicos bajos y que comienzan a usarse en grupos sociales más altos en función de emular el comportamiento de aquellos. Aunque la gramática prescriptiva aún suele utilizarse en pedagogía y en la enseñanza de lenguas extranjeras, ha perdido peso en la lingüística académica moderna, y actualmente describe solamente un subconjunto del uso de la lengua. La gramática descriptiva intenta describir el uso actual de una lengua, evitando juzgar en forma prescriptiva. Se vincula a una determinada comunidad hablante y pretende proveer reglas de uso para cualquier palabra considerada gramáticamente correcta en esa comunidad. La gramática tradicional es la colección de ideas acerca de la gramática que las sociedades occidentales han heredado de Grecia y Roma. La gramática prescriptiva es formulada usualmente en términos de los conceptos descriptivos heredados de la gramática tradicional. La gramática descriptiva moderna apunta a corregir los errores de la gramática tradicional, y generaliza su normativa restrictiva para evitar circunscribir los lenguajes al modelo del latín. La gramática funcional, es una visión general sobre la organización del lenguaje natural, formulada por Simon Dik, que contempla tres normas básicas de adecuación: la tipológica, que implica la aplicación de reglas a cualquier lengua, la pragmática, que promueve la aplicación de los enunciados a la interacción en la comunicación, y la psicológica, por la que trata de ser compatible con los mecanismos psicológicos involucrados en el procesamiento de un lenguaje natural.[1] La gramática generativa es un enfoque formal para el estudio sintáctico de las lenguas que puede en algunos sentidos generar las expresiones bien construidas de una lengua natural. Una rama de la teoría lingüística (psicolingüística) se basa en la gramática generativa, promovida por Noam Chomsky. Las gramáticas formales aparecen en lingüística computacional. La sintaxis de cada lenguaje de programación se define de hecho por una gramática formal. En teoría de la informática y en matemática, la gramática formal define lenguajes formales. La Jerarquía de Chomsky describe varias clases importantes de gramática formal.


Historia de la teoría gramatical

Gramática del hebreo por Judah Monis, publicada por primera vez en 1735 para los alumnos de Harvard La? teoría gramatical ha evolucionado a través del uso y la división de las poblaciones humanas y las reglas sobre el uso del lenguaje tendieron a aparecer con el advenimiento de la escritura. La gramática más antigua que se conoce es el Astadhiaia, un estudio sobre el sánscrito, escrito por Pánini, en la India, hacia el año 480 a. C. Aunque Sócrates, Aristóteles y otros sabios de la antigüedad disertaron sobre la gramática, el primer tratado completo de gramática griega fue el que compuso Grates de Malos (siglo II a. C.). Por otra parte la Ars Grammatica de Elio Donato (s. IV) dominó los estudios gramaticales durante la Edad Media.

La gramática formal es una codificación del uso desarrollada basándose en la observación. Al establecerse y desarrollarse las reglas, pudo aparecer el concepto prescriptivo, que a menudo creó una brecha entre el uso contemporáneo y lo aceptado como correcto. Los lingüistas consideran normalmente que la gramática prescriptiva no tiene justificación alguna más allá del gusto estético de sus autores. De cualquier forma, las prescripciones permiten a la sociolingüística explicar las razones por las que un determinado grupo social utiliza construcciones diferenciales.

El estudio formal de la gramática es una parte importante de la educación desde la edad temprana hasta el aprendizaje avanzado, aunque las reglas que se enseñan en las escuelas no constituyen una gramática en el sentido en que los lingüistas utilizan el término, ya que son prescriptivas antes que descriptivas.

Los lenguajes construidos son muy comunes en la actualidad. Muchos —como el esperanto— fueron diseñados para ayudar en la comunicación humana, o el lojban, altamente compatible con lenguajes artificiales. También se han creado lenguajes como parte de un mundo de ficción (como el klingon y el quenya), y cada uno de ellos tiene su propia gramática.


Lenguaje Formal:

En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.

Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, en derecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal, en el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir métodos computacionales. Sin embargo, hoy en día, el punto de vista de que la naturaleza esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido informal antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes formales (en el sentido estricto de este artículo) gana cada vez más adeptos.

Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos a que b, por ejemplo.

La palabra vacía (esto es, la cadena de longitud cero) es permitida y frecuentemente denotada mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud también finita, un lenguaje puede bien incluir un número infinito de palabras.

Algunos ejemplos varios de lenguajes formales:

el conjunto de todas las palabras sobre {a, b} el conjunto {an: n es un número primo} el conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación el conjunto de entradas para las cuales una particular máquina de Turing se detiene. Los lenguajes formales pueden ser especificados en una amplia variedad de maneras, como:

cadenas producidas por una gramática formal (ver Jerarquía de Chomsky) cadenas producidas por una expresión regular cadenas aceptadas por un autómata, tal como una máquina de Turing Varias operaciones pueden ser utilizadas para producir nuevos lenguajes a partir de otros dados. Supóngase que L1 y L2 son lenguajes sobre un alfabeto común. Entonces:

la concatenación L 1 L 2 consiste de todas aquellas palabras de la forma vw donde v es una palabra de L1 y w es una palabra de L2 la intersección L1&L2 consiste en todas aquellas palabras que están contenidas tanto en L1 como en L2 la unión L1|L2 consiste en todas aquellas palabras que están contenidas ya sea en L1 o en L2 el complemento ~L1 consiste en todas aquellas palabras producibles sobre el alfabeto de L1 que no están ya contenidas en L1 el cociente L1/L2 consiste de todas aquellas palabras v para las cuales existe una palabra w en L2 tales que vw se encuentra en L1 la estrella L1*</sub› consiste de todas aquellas palabras que pueden ser escritas de la forma W 1 W 2…Wn donde todo Wi se encuentra en L1 y n ≥ 0. (Nótese que esta definición incluye a ε en cualquier L*) la intercalación L1*L1 consiste de todas aquellas palabras que pueden ser escritas de la forma v1w1v2w2…vnwn son palabras tales que la concatenación v1…vn está en L1, y la concatenación w1…wn está en L2 Una pregunta que se hace típicamente sobre un determinado lenguaje formal L es cuán difícil es decidir si incluye o no una determinada palabra v. Este tema es del dominio de la teoría de la computabilidad y la teoría de la complejidad computacional.

Por contraposición al lenguaje propio de los seres vivos y en especial el lenguaje humano, considerados lenguajes naturales, se denomina lenguaje formal a los lenguajes «artificiales» propios de las matemáticas o la informática, los lenguajes artificiales son llamados lenguajes formales (incluyendo lenguajes de programación). Sin embargo, el lenguaje humano tiene una característica que no se encuentra en los lenguajes de programación: la diversidad.

En 1956, Noam Chomsky creó la Jerarquía de Chomsky para organizar los distintos tipos de lenguaje formal.


http://es.youtube.com/watch?v=QnMo5OVYZyo


grado: 1-B
maestro: Alberto Lomeli.
integrantes:

             Mata Leon Juan Carlos
             Acevedo Estrada Juan Antonio
             Gonzales Tafolla Demetrio de Jesus
             Ortega Romero Christian 


Mis sitios nuevos:
Emprendedores
Politica de Privacidad