Lenguaje formal

Esta imagen muestra la relación entre las cadenas de caracteres, las fórmulas bien formadas y los teoremas. En algunos 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 primitivos y reglas para unir esos símbolos están formalmente especificados.[2] 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.

En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante , o .

Ejemplo de lenguajes formales

Other Languages
العربية: لغة شكلية
български: Формален език
bosanski: Formalni jezik
کوردیی ناوەندی: زمانی شێوەیی
čeština: Formální jazyk
Ελληνικά: Τυπική γλώσσα
Esperanto: Formala lingvo
فارسی: زبان صوری
français: Langage formel
hrvatski: Formalni jezik
日本語: 形式言語
한국어: 형식 언어
lietuvių: Formali kalba
македонски: Формален јазик
Mirandés: Lenguaige formal
Nederlands: Formele taal
norsk bokmål: Formelt språk
português: Linguagem formal
română: Limbaje formale
srpskohrvatski / српскохрватски: Formalni jezik
Simple English: Formal language
slovenčina: Formálny jazyk
српски / srpski: Формални језик
українська: Формальна мова
Tiếng Việt: Ngôn ngữ hình thức
中文: 形式语言