Diferencia entre revisiones de «Lenguaje formal»
Contenido eliminado Contenido añadido
Sin resumen de edición Etiquetas: Revertido posibles pruebas |
m Revertidos los cambios de 2806:2F0:92C0:EBB9:A97D:5398:BA48:4755 (disc.) a la última edición de SeroBOT Etiqueta: Reversión |
||
Línea 1:
{{otros usos|Lenguaje formalizado}}
[[Archivo:Entidades sintácticas 3.svg|thumb|230px|right|Esta imagen muestra la relación entre las [[Cadena de caracteres|cadenas de caracteres]], las [[Fórmula bien formada|fórmulas bien formadas]] y los [[teorema]]s. En algunos [[sistema formal|sistemas formales]], sin embargo, el conjunto de los teoremas coincide con el de las fórmulas bien formadas.]]
En [[matemáticas]], [[lógica]] y [[ciencias de la computación]], un '''lenguaje formal''' es un [[lenguaje]] cuyos símbolos son
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 [[Lenguaje natural|lenguajes naturales]].
En algunos lenguajes formales, la ''palabra vacía'' (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante <math>\epsilon \,</math>, <math>e\,</math> o <math>\lambda \,</math>.
== Ejemplo de lenguajes formales ==
* La [[Numeración de Gödel]] {''a''<sup>''n''</sup> : ''a'' es un [[número primo]] y ''n'' un número de Gödel}.
* 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]].
== Especificación de lenguajes formales ==
Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por ejemplo:
(Si el lenguaje es regular)
|