Lenguaje formal

Un lenguaje formal en lógica matemática , informática y lingüística es un conjunto de palabras finitas (cadenas, cadenas) sobre un alfabeto finito . El concepto de lenguaje se usa más comúnmente en la teoría de autómatas , la teoría de la computabilidad y la teoría de algoritmos . La teoría científica que se ocupa de este objeto se denomina teoría de los lenguajes formales .

En la teoría de modelos, un lenguaje se construye a partir de conjuntos de símbolos, funciones y relaciones , junto con su aridad , así como un conjunto de variables . Cada uno de estos conjuntos puede ser infinito. A partir del lenguaje, junto con los símbolos lógicos universales , se elaboran enunciados lógicos.

Definición

Un lenguaje formal se puede definir de varias maneras, por ejemplo:

Una simple enumeración de las palabras incluidas en un idioma dado. Este método es principalmente aplicable a la definición de lenguajes finitos y lenguajes de estructura simple.
Palabras generadas por alguna gramática formal (ver Jerarquía de Chomsky ).
Palabras generadas por la expresión regular .
Palabras reconocidas por alguna máquina de estado .
Palabras generadas por la construcción BNF .

Por ejemplo, si el alfabeto se da como , y el idioma incluye todas las palabras anteriores, entonces la palabra pertenece a . La palabra vacía (es decir, una cadena de longitud cero) está permitida y, a menudo, se denota como , o . $\{a,b\}$ $L$ $ababba$ $L$ $mi$ $\epsilon$ $\lambda$

Algunos otros ejemplos de lenguajes formales:

set , donde es un número no negativo , y significa que se repite varias veces; $\{a^{n}\}$ $norte$ $un^{{n}}$ $a$ $norte$
el conjunto de programas sintácticamente correctos en un lenguaje de programación dado .

Operaciones

Algunas operaciones se pueden utilizar para generar nuevos idiomas a partir de datos. Supongamos que y son lenguas definidas sobre algún alfabeto común. $L_{{1}}$ $L_{{2}}$

La concatenación (enlace) contiene todas las palabras que satisfacen la forma , donde es una palabra de y es una palabra de . $L_{{1}}L_{{2}}$ $volvo$ $v$ $L_{{1}}$ $w$ $L_{{2}}$
La intersección contiene todas las palabras contenidas en , y . $L_{1}\cap L_{2}$ $L_{1}$ $L_{{2}}$
La unión contiene todas las palabras contenidas en o en . $L_{1}\taza L_{2}$ $L_{{1}}$ $L_{{2}}$
El complemento de idioma contiene todas las palabras del alfabeto que no están contenidas en . $L_{{1}}$ $L_{{1}}$
La relación correcta contiene todas las palabras para las que hay una palabra en tal que estaba en . $L_{{1}}/L_{{2}}$ $v$ $w$ $L_{{2}}$ $volvo$ $L_{{1}}$
El cierre de Kleene contiene todas las palabras que se pueden escribir en la forma en que está contenido en y . Tenga en cuenta que esto también incluye la palabra vacía , ya que la condición lo permite. $L_{{1}}^{{*}}$ $w_{{1}}w_{{2}}...w_{{n}}$ $Wisconsin}}$ $L_{{1}}$ $n\geq 0$ $\epsilon$ $n=0$
La inversión contiene palabras invertidas de . $L_{{1}}^{{R}}$ $L_{{1}}$
La confusión y contiene todas las palabras que se pueden escribir en la forma , donde y son palabras tales que la relación está en , y son tales palabras que están en . $L_{{1}}$ $L_{{2}}$ $v_{{1}}w_{{1}}v_{{2}}w_{{2}}...v_{{n}}w_{{n}}$ $n\geq 1$ $v_{{1}},...,v_{{n}}$ $v_{{1}}...v_{{n}}$ $L_{{1}}$ $w_{{1}},...,w_{{n}}$ $w_{{1}}...w_{{n}}$ $L_{{2}}$

Véase también

semántica formal

Literatura

Gladkiy A. V. Gramáticas y lenguajes formales. — M.: Nauka, 1973. — 368 p.
Hopcroft J. , Motwani R. , Ullman J. Introducción a la teoría de autómatas, lenguajes y computación. - M.: Williams, 2002 (traducido por Addison Wesley). — 528 pág. — ISBN 5-8459-0261-4
Krevskiy I. G., Seliverstov M. N., Grigoryeva K. V. Lenguajes formales, gramáticas y conceptos básicos de la construcción de traductores: Libro de texto / Ed. A. M. Bershadsky. - Penza: Editorial Penz. estado un-ta, 2002. - 124 p.
Martynenko B.K. Idiomas y traducciones: Libro de texto. - San Petersburgo: Editorial de la Universidad de San Petersburgo, 2003. - 235 p.
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoría e implementación de lenguajes de programación - M.: MZ-Press, 2006, 2ª ed. — ISBN 5-94073-094-9
Pentus A. E., Pentus M. R. Teoría matemática de los lenguajes formales. - M.: Internet Universidad de Tecnologías de la Información, Binom. Laboratorio del Conocimiento, 2006. - 248 p.
Fomichev V. S. Lenguajes formales, gramáticas y autómatas: Curso de conferencias - Publicación en Internet, 2006.
B. V. Biryukov. Lenguaje formalizado // Nueva Enciclopedia Filosófica : en 4 volúmenes / anterior. ed. científica consejo de V. S. Stepin . — 2ª ed., corregida. y adicional - M. : Pensamiento , 2010. - 2816 p.

diccionarios y enciclopedias

En catálogos bibliográficos
BNF : 11967270h TIERRA : 4017848-1 J9U : 987007545721205171 LCCN : sh85050802 NDL : 00576869 NKC : ph208851

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami