Tipos De Lenguaje

TIPOS DE LENGUAJE
LENGUAJE FORMAL
En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas apartir de un alfabeto (conjunto de caracteres) finito.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobreeste 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 delongitud 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 incluirun 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 detodos 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.

Loslenguajes formales pueden ser especificados en una amplia variedad de maneras, como:
• Cadenas producidas por una gramática formal
• Cadenas producidas por una expresión regular
• Cadenasaceptadas 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 sonlenguajes 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
• Laintersecció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