Lenguaje formal - Historial de revisiones

Luzzzz: /* Definició */

2021-02-02T04:18:35Z

‎Definició

Luzzzz: /* Definición */

2021-02-02T04:18:00Z

‎Definición

Carlos idict en 20:55 16 may 2013

2013-05-16T20:55:03Z

Yunesky jc.mtz: /* Véase también */

2013-04-18T12:36:39Z

‎Véase también

Rey1103jc en 16:55 4 abr 2013

2013-04-04T16:55:58Z

Jhonlier12017 jc.hlg: /* Operaciones en idiomas */

2012-02-21T20:53:17Z

‎Operaciones en idiomas

Maria ciget.cienfuegos: /* Operaciones en idiomas */

2011-02-10T14:21:59Z

‎Operaciones en idiomas

Maria ciget.cienfuegos en 14:20 10 feb 2011

2011-02-10T14:20:33Z

Juan M dirjc.pri en 19:38 3 feb 2011

2011-02-03T19:38:06Z

Pinar8 jc: Página creada con '{{Definición|Nombre=Lenguaje_Formal|imagen=Lenguaje_Formal.jpg|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El i...'

2011-01-28T16:53:28Z

Página creada con '{{Definición|Nombre=Lenguaje_Formal|imagen=Lenguaje_Formal.jpg|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El i...'

Página nueva

{{Definición|Nombre=Lenguaje_Formal|imagen=Lenguaje_Formal.jpg|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}} 

== Definición: ==

En matemáticas, [[Lógica]], y [[Ciencias de la computación]], un lenguaje formal es un lenguaje cuyos [[Símbolos]] primitivos y reglas para unir esos símbolos están formalmente especificados. 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). 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. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus [[Fórmulas]] bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas. Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas. 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. 

== Ejemplos de lenguajes formales: ==

* Un 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 todas las fórmulas bien formadas en la lógica de primer orden. 

== Formalismos de la especificación de la lengua: ==

La teoría del lenguaje formal se refiere raramente a [[Idiomas]] particulares (excepto como ejemplos), pero se trata principalmente al estudio de varios tipos de formalismos para describir idiomas. Por ejemplo, una lengua se puede dar como

*Un sistema de las secuencias que se pueden generar por alguno gramática formal (véase [[Jerarquía de Chomsky]]); * Un sistema de secuencias descritas o emparejadas por un detalle expresión regular; * Un sistema de secuencias aceptadas por alguno autómata, por ejemplo a [[Máquina de Turing]] o autómata finito del estado; * Un sistema de las secuencias para las cuales algunos procedimiento de la decisión ( algoritmo que pide una secuencia de las preguntas relacionadas de YES/NO) produce la respuesta SÍ.

Las preguntas típicas preguntaron por tales formalismos incluyen:

*¿Cuál es su energía expresiva? ¿(Puede el formalismo X describir cada lengua que el formalismo Y pueda describir? Puede describir otras idiomas?) * ¿Cuál es su recognizability? (Cómo es difícil es para decidir a si una palabra dada pertenece a una lengua descrita por el formalismo X?) * ¿Cuál es su comparabilidad? (Cómo es difícil es para decidir a si dos idiomas, una descrita en el formalismo X y uno en el formalismo Y, o en X otra vez, son realmente la misma lengua?).

Asombrosamente a menudo, la respuesta a estos problemas de la decisión es “él no se puede hacer en todos”, o “es extremadamente costosa” (con una caracterización exacta de cómo es costoso exactamente). Por lo tanto, la teoría del lenguaje formal es un área de aplicación importante de teoría del computability y teoría de complejidad. 

== Operaciones en idiomas: ==

Se pueden utilizar varias operaciones 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 L1L2 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 W1W2...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. 

== Verdades concernientes a los lenguajes formales: ==

Teorema 1 El conjunto de lenguajes en general (incluyendo los no-formales) es incontable. Lema 1 El conjunto de lenguajes en un alfabeto no vacío dado es incontable. Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto es incontable. Como sabemos, un lenguaje L en es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en es justamente (el conjunto de todos los subconjuntos o conjunto potencia de ) y es evidente que es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un [[Conjunto infinito]] de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado. Demostración del Teorema 1 Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable. Teorema 2 Los lenguajes son [[Conjuntos contables]]. Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado. Teorema 3 El conjunto de lenguajes formales es contable. Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de ) y como es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida. 

== Véase también: ==

*[[Gramática formal]]
* [[Marco de la gramática]]
* [[Método formal]]
* [[Ciencia formal]]
* [[Sistema formal]]
* [[Notación matemática]]
* [[Lenguaje de programación]] 

== Enlaces externos: ==

[http://www.worldlingo.com Worldlingo.com] 

== Fuente: ==

[http://www.worldlingo.com www.worldlingo.com] 

 

 

 

[[Category:Comunicación]]

@@ Línea 3: / Línea 3: @@
 '''Lenguaje formal'''. Es aquel que el hombre ha desarrollado para expresar las situaciones que se dan en especifico en cada área del conocimiento científico. Las palabras y oraciones de un lenguaje formal son perfectamente definidas. Pueden ser utilizados para modelar una teoría de la [[mecánica]], [[física]], [[matemática]], [[ingeniería eléctrica]], o de otra naturaleza, con la ventaja de que en estos toda ambigüedad es eliminada.
-== Definició ==
+== Definición ==
 En matemáticas, [[Lógica]], y [[Ciencias de la computación]], un lenguaje formal es un lenguaje cuyos [[Símbolos]] primitivos y reglas para unir esos símbolos están formalmente especificados. 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). 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. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus [[Fórmulas]] bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.<br>Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.<br>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.

@@ Línea 3: / Línea 3: @@
 '''Lenguaje formal'''. Es aquel que el hombre ha desarrollado para expresar las situaciones que se dan en especifico en cada área del conocimiento científico. Las palabras y oraciones de un lenguaje formal son perfectamente definidas. Pueden ser utilizados para modelar una teoría de la [[mecánica]], [[física]], [[matemática]], [[ingeniería eléctrica]], o de otra naturaleza, con la ventaja de que en estos toda ambigüedad es eliminada.
-== Definición ==
+== Definició ==
 En matemáticas, [[Lógica]], y [[Ciencias de la computación]], un lenguaje formal es un lenguaje cuyos [[Símbolos]] primitivos y reglas para unir esos símbolos están formalmente especificados. 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). 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. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus [[Fórmulas]] bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.<br>Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.<br>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.
@@ Línea 40: / Línea 40: @@
 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.<br>
-== Verdades concernientes a los lenguajes formales:<br>  ==
+== Verdades concernientes a los lenguajes formales:   ==
 Teorema 1<br>El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.<br>Lema 1<br>El conjunto de lenguajes en un alfabeto no vacío dado es incontable.<br>Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto es incontable. Como sabemos, un lenguaje L en es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en es justamente (el conjunto de todos los subconjuntos o conjunto potencia de ) y es evidente que es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un [[Conjunto infinito]] de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado.<br>Demostración del Teorema 1<br>Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable.<br>Teorema 2<br>Los lenguajes son [[Conjuntos contables]].<br>Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado.<br>Teorema 3<br>El conjunto de lenguajes formales es contable.<br>Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de ) y como es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida.<br>

@@ Línea 9: / Línea 9: @@
 == Ejemplos de lenguajes formales ==
-*&nbsp;Un conjunto de todas las [[Palabras]] sobre {a,b}.
+*&nbsp;Un conjunto de todas las [[Palabra]]s sobre {a,b}.
 *&nbsp;El conjunto {an&nbsp;: n} es un número primo.
 *&nbsp;El conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación.

← Revisión anterior		Revisión del 12:36 18 abr 2013
Línea 43:		Línea 43:

	Teorema 1<br>El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.<br>Lema 1<br>El conjunto de lenguajes en un alfabeto no vacío dado es incontable.<br>Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto es incontable. Como sabemos, un lenguaje L en es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en es justamente (el conjunto de todos los subconjuntos o conjunto potencia de ) y es evidente que es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un [[Conjunto infinito]] de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado.<br>Demostración del Teorema 1<br>Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable.<br>Teorema 2<br>Los lenguajes son [[Conjuntos contables]].<br>Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado.<br>Teorema 3<br>El conjunto de lenguajes formales es contable.<br>Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de ) y como es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida.<br>		Teorema 1<br>El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.<br>Lema 1<br>El conjunto de lenguajes en un alfabeto no vacío dado es incontable.<br>Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto es incontable. Como sabemos, un lenguaje L en es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en es justamente (el conjunto de todos los subconjuntos o conjunto potencia de ) y es evidente que es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un [[Conjunto infinito]] de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado.<br>Demostración del Teorema 1<br>Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable.<br>Teorema 2<br>Los lenguajes son [[Conjuntos contables]].<br>Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado.<br>Teorema 3<br>El conjunto de lenguajes formales es contable.<br>Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de ) y como es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida.<br>
−
−	~~== Véase también ==~~
−
−	*[[Gramática formal]]
−	* [[Marco de la gramática]]
−	* [[Método formal]]
−	* [[Ciencia formal]]
−	* [[Sistema formal]]
−	* [[Notación matemática]]
−	* [[Lenguaje de programación]]

	== Enlaces externos ==		== Enlaces externos ==

← Revisión anterior		Revisión del 16:55 4 abr 2013
Línea 1:		Línea 1:
−	{{Definición\|Nombre=Lenguaje_Formal\|imagen=~~Lenguaje_Formal~~.jpg\|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}	+	{{Definición\|Nombre=Lenguaje_Formal\|imagen=Lenguaje_formal.jpg\|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}

	'''Lenguaje formal'''. Es aquel que el hombre ha desarrollado para expresar las situaciones que se dan en especifico en cada área del conocimiento científico. Las palabras y oraciones de un lenguaje formal son perfectamente definidas. Pueden ser utilizados para modelar una teoría de la [[mecánica]], [[física]], [[matemática]], [[ingeniería eléctrica]], o de otra naturaleza, con la ventaja de que en estos toda ambigüedad es eliminada.		'''Lenguaje formal'''. Es aquel que el hombre ha desarrollado para expresar las situaciones que se dan en especifico en cada área del conocimiento científico. Las palabras y oraciones de un lenguaje formal son perfectamente definidas. Pueden ser utilizados para modelar una teoría de la [[mecánica]], [[física]], [[matemática]], [[ingeniería eléctrica]], o de otra naturaleza, con la ventaja de que en estos toda ambigüedad es eliminada.

@@ Línea 30: / Línea 30: @@
 Se pueden utilizar varias operaciones para producir nuevos lenguajes a partir de otros dados. Supóngase que L1 y L2 son lenguajes sobre un alfabeto común. Entonces.
-*&nbsp;La concatenación L1L2 consiste de todas aquellas palabras de la forma vw donde v es una palabra de L1 y w es una palabra de L2
+* La concatenación L1L2 consiste de todas aquellas palabras de la forma vw donde v es una palabra de L1 y w es una palabra de L2
-*&nbsp;La intersección L1&amp;L2 consiste en todas aquellas palabras que están contenidas tanto en L1 como en L2
+* La intersección L1&amp;L2 consiste en todas aquellas palabras que están contenidas tanto en L1 como en L2
-*&nbsp;La unión L1|L2 consiste en todas aquellas palabras que están contenidas ya sea en L1 o en L2
+* La unión L1|L2 consiste en todas aquellas palabras que están contenidas ya sea en L1 o en L2
-*&nbsp;El complemento ~L1 consiste en todas aquellas palabras producibles sobre el alfabeto de L1 que no están ya contenidas en L1
+* El complemento ~L1 consiste en todas aquellas palabras producibles sobre el alfabeto de L1 que no están ya contenidas en L1
-*&nbsp;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
+* 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
-*&nbsp;La [[Estrella]] L1* consiste de todas aquellas palabras que pueden ser escritas de la forma W1W2...Wn donde todo Wi se encuentra en L1 y n ≥ 0. (Nótese que esta definición incluye a ε en cualquier L*)
+* La [[Estrella]] L1* consiste de todas aquellas palabras que pueden ser escritas de la forma W1W2...Wn donde todo Wi se encuentra en L1 y n ≥ 0. (Nótese que esta definición incluye a ε en cualquier L*)
-*&nbsp;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
+* 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.<br>
+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.<br>
 == Verdades concernientes a los lenguajes formales:<br>  ==

← Revisión anterior		Revisión del 14:20 10 feb 2011
Línea 1:		Línea 1:
	{{Definición\|Nombre=Lenguaje_Formal\|imagen=Lenguaje_Formal.jpg\|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}		{{Definición\|Nombre=Lenguaje_Formal\|imagen=Lenguaje_Formal.jpg\|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}
		+
		+	'''Lenguaje formal'''. Es aquel que el hombre ha desarrollado para expresar las situaciones que se dan en especifico en cada área del conocimiento científico. Las palabras y oraciones de un lenguaje formal son perfectamente definidas. Pueden ser utilizados para modelar una teoría de la [[mecánica]], [[física]], [[matemática]], [[ingeniería eléctrica]], o de otra naturaleza, con la ventaja de que en estos toda ambigüedad es eliminada.

	== Definición ==		== Definición ==

@@ Línea 1: / Línea 1: @@
-{{Definición|Nombre=Lenguaje_Formal|imagen=Lenguaje_Formal.jpg|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}<br>
+{{Definición|Nombre=Lenguaje_Formal|imagen=Lenguaje_Formal.jpg|concepto=El lenguaje formal es un sistema de palabras, es decir finito de secuencias de letras, o símbolos. El inventario del cual se toman estas letras se llama alfabeto sobre cuál se define la lengua. Un lenguaje formal se define a menudo por medio de una gramática formal.}}
-== Definición:<br>  ==
+== Definición ==
-En matemáticas, [[Lógica]], y [[Ciencias de la computación]], un lenguaje formal es un lenguaje cuyos [[Símbolos]] primitivos y reglas para unir esos símbolos están formalmente especificados. 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). 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. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus [[Fórmulas]] bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.<br>Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.<br>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.<br>
+En matemáticas, [[Lógica]], y [[Ciencias de la computación]], un lenguaje formal es un lenguaje cuyos [[Símbolos]] primitivos y reglas para unir esos símbolos están formalmente especificados. 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). 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. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus [[Fórmulas]] bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.<br>Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.<br>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.
-== Ejemplos de lenguajes formales:<br>  ==
+== Ejemplos de lenguajes formales ==
 *&nbsp;Un conjunto de todas las [[Palabras]] sobre {a,b}.
 *&nbsp;El conjunto {an&nbsp;: n} es un número primo.
 *&nbsp;El conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación.
-*El conjunto de todas las fórmulas bien formadas en la lógica de primer orden.<br>
+*El conjunto de todas las fórmulas bien formadas en la lógica de primer orden.
-== Formalismos de la especificación de la lengua:<br>  ==
+== Formalismos de la especificación de la lengua ==
 La teoría del lenguaje formal se refiere raramente a [[Idiomas]] particulares (excepto como ejemplos), pero se trata principalmente al estudio de varios tipos de formalismos para describir idiomas. Por ejemplo, una lengua se puede dar como
@@ Línea 20: / Línea 20: @@
 Las preguntas típicas preguntaron por tales formalismos incluyen:
-*¿Cuál es su energía expresiva? ¿(Puede el formalismo X describir cada lengua que el formalismo Y pueda describir? Puede describir otras idiomas?)<br> * ¿Cuál es su recognizability? (Cómo es difícil es para decidir a si una palabra dada pertenece a una lengua descrita por el formalismo X?)<br> * ¿Cuál es su comparabilidad? (Cómo es difícil es para decidir a si dos idiomas, una descrita en el formalismo X y uno en el formalismo Y, o en X otra vez, son realmente la misma lengua?).
+*¿Cuál es su energía expresiva? ¿(Puede el formalismo X describir cada lengua que el formalismo Y pueda describir? Puede describir otras idiomas?)<br> *¿Cuál es su recognizability? (Cómo es difícil es para decidir a si una palabra dada pertenece a una lengua descrita por el formalismo X?)<br> *¿Cuál es su comparabilidad? (Cómo es difícil es para decidir a si dos idiomas, una descrita en el formalismo X y uno en el formalismo Y, o en X otra vez, son realmente la misma lengua?).
-Asombrosamente a menudo, la respuesta a estos problemas de la decisión es “él no se puede hacer en todos”, o “es extremadamente costosa” (con una caracterización exacta de cómo es costoso exactamente). Por lo tanto, la teoría del lenguaje formal es un área de aplicación importante de teoría del computability y teoría de complejidad.<br>
+Asombrosamente a menudo, la respuesta a estos problemas de la decisión es “él no se puede hacer en todos”, o “es extremadamente costosa” (con una caracterización exacta de cómo es costoso exactamente). Por lo tanto, la teoría del lenguaje formal es un área de aplicación importante de teoría del computability y teoría de complejidad.
-== Operaciones en idiomas:<br>  ==
+== Operaciones en idiomas  ==
-Se pueden utilizar varias operaciones para producir nuevos lenguajes a partir de otros dados. Supóngase que L1 y L2 son lenguajes sobre un alfabeto común. Entonces:<br>
+Se pueden utilizar varias operaciones para producir nuevos lenguajes a partir de otros dados. Supóngase que L1 y L2 son lenguajes sobre un alfabeto común. Entonces.
 *&nbsp;La concatenación L1L2 consiste de todas aquellas palabras de la forma vw donde v es una palabra de L1 y w es una palabra de L2
@@ Línea 36: / Línea 36: @@
 *&nbsp;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]].<br>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.<br>En [[1956]], [[Noam Chomsky]] creó la jerarquía de Chomsky para organizar los distintos tipos de lenguaje formal.<br>
+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.<br>
 == Verdades concernientes a los lenguajes formales:<br>  ==
@@ Línea 42: / Línea 42: @@
 Teorema 1<br>El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.<br>Lema 1<br>El conjunto de lenguajes en un alfabeto no vacío dado es incontable.<br>Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto es incontable. Como sabemos, un lenguaje L en es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en es justamente (el conjunto de todos los subconjuntos o conjunto potencia de ) y es evidente que es infinito (de hecho; contable), también ha sido demostrado que si A es un conjunto infinito (contable o incontable), entonces 2A es mayor que A porque 2A pasa a ser un [[Conjunto infinito]] de órdenes del infinito, al ser mayor, no existirá biyección entre A y 2A, lo que hace a 2A un conjunto infinito incontable, la prueba ha finalizado.<br>Demostración del Teorema 1<br>Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo 2A, donde A es un conjunto infinito contable.<br>Teorema 2<br>Los lenguajes son [[Conjuntos contables]].<br>Se sabe que un lenguaje L en un alfabeto Σ es un subconjunto de Σ * y como ya se hizo mención, Σ * es infinito contable, por ende, L es como mucho un conjunto infinito contable (del mismo tamaño que Σ * ), la prueba ha culminado.<br>Teorema 3<br>El conjunto de lenguajes formales es contable.<br>Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre A y B"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos X) y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de ) y como es contable, ese subconjunto también será contable y como existe dicha biyección (entre X e Y), la aserción ha sido demostrada, prueba concluida.<br>
-== Véase también:<br>  ==
+== Véase también ==
 *[[Gramática formal]]
@@ Línea 50: / Línea 50: @@
 *&nbsp;[[Sistema formal]]
 *&nbsp;[[Notación matemática]]
-*&nbsp;[[Lenguaje de programación]]<br>
+*&nbsp;[[Lenguaje de programación]]
-== Enlaces externos:<br>  ==
+== Enlaces externos ==
-[http://www.worldlingo.com Worldlingo.com]<br>
+[http://www.worldlingo.com Worldlingo.com]
-== Fuente:<br>  ==
+== Fuente ==
 [http://www.worldlingo.com www.worldlingo.com]<br>
 [[Category:Comunicación]]