lenguajes y cadenas
En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres)
cadenas de caracteres
En matemáticas, una cadena de caracteres, palabra o frase es una secuencia ordenada de longitud arbitraria (aunque finita) de elementos que pertenecen a un cierto alfabeto. Habitualmente se usan las letras w, x, y,… para referirnos a cadenas. Por ejemplo, si tenemos un alfabeto Σ = {a, b, c}, una cadena podría ser: x = aacbbcba.
En general, una cadena de caracteres es una sucesión de caracteres (letras, números o determinados signos). Se utilizan en programación, normalmente como un tipo de dato predefinido, para palabras, frases o cualquier otra sucesión de caracteres.
Es muy habitual que se delimiten mediante comillas superiores (“). Para poder mostrar, por ejemplo, una comilla (“) dentro de la cadena y no tener problemas con las comillas que la delimitan, se usan secuencias de escape. Esto se aplica a otros caracteres reservados o no imprimibles como el retorno de carro. No obstante, las expresiones para producir estas secuencias de escape dependen del lenguaje de programación que se esté usando. Una forma común, en muchos lenguajes, de escapar un carácter es anteponiéndole un «\» (sin comillas), p. e.: «\”» (sin comillas).
Algunas operaciones comunes
Concatenación: unir dos cadenas de caracteres.
$pareja = “Luis”.” y “.”Carmen” # en Perl y PHP;
pareja = “Luis” & “ y “ & “Carmen” # en Visual Basic;
pareja = “Luis” + “ y “ + “Carmen”; # en C++ con la clase String.
String pareja = “Luis”+ “ y “ + “Carmen”; # en Java con la clase String
Multiplicar una cadena: repetir una cadena un número de veces
$puntos =“.” x 5 # pone 5 puntos en Perl
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
