Ir al contenido principal

Lenguajes

  Lenguajes 

Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denomina lenguaje. Si Σ es un alfabeto y L ⊆ Σ∗, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos establecido que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un superconjunto de Σ. 

La elección del término “lenguaje” puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo sería el inglés, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C, o cualquier otro lenguaje de programación, donde los programas correctos son un subconjunto de las posibles cadenas que pueden formarse a partir del alfabeto del lenguaje. Este alfabeto es un subconjunto de los caracteres ASCII. El alfabeto en concreto puede diferir ligeramente entre diferentes lenguajes de programación, aunque generalmente incluye las letras mayúsculas y minúsculas, los dígitos, los caracteres de puntuación y los símbolos matemáticos.

La única restricción importante sobre lo que puede ser un lenguaje es que todos los alfabetos son finitos. De este modo, los lenguajes, aunque pueden tener un número infinito de cadenas, están restringidos a que dichas cadenas estén formadas por los símbolos que definen un alfabeto finito y prefijado.


Definición de lenguajes mediante descripciones de conjuntos.

Es habitual describir un lenguaje utilizando una “descripición de conjuntos”: 

{w | algo acerca de w} 

Esta expresión se lee “el conjunto de palabras w tal que (lo que se dice acerca de w a la derecha de la barra vertical)”. Algunos ejemplos son: 

1. {w | w consta de un número igual de ceros que de unos }. 

2. {w | w es un entero binario que es primo }. 

3. {w | w es un programa C sintácticamente correcto }. 

También es habitual reemplazar w por alguna expresión con parámetros y describir las cadenas del lenguaje estableciendo condiciones sobre los parámetros. 



Video sobre loa lenguajes autómatas.






Comentarios

Publicar un comentario

Entradas más populares de este blog

3.1 CONCEPTO DEFINICIÓN Y CLASIFICACIÓN DE AUTÓMATA FINITO (AF)

Autómata  finito. es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida. La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky. Definición formal Formalmente: E: alfabeto de entrada. Q: conjunto de estados; es conjunto finito no vacío. f: función de transición. f(p, a)=q q0 : (perteneciente a Q) estado inicial. F : (perteneciente a Q) conjunto de estados finales o de ac...
Publicar un comentario
Leer más

1.3 Lenguajes, tipos y herramientas

LENGUAJES: Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un súper conjunto de Σ. La elección del termino "lenguaje" puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el Ingles, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.   Tipos de lenguajes: LENGUAJE NATURAL:  Nosotros estamos relacionados con el concepto tradicional de gramática que, de esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos indican que es correcto y que no lo es del...
Publicar un comentario
Leer más

Expresiones Regulares

Definición . Las expresiones regulares pueden definir de forma exacta los mismos lenguajes que describen los distintos tipos de autómatas: los lenguajes regulares. Sin embargo, las expresiones regulares ofrecen algo que los autómatas no proporcionan: una forma declarativa para expresar las cadenas que deseamos aceptar. Antes de describir la notación de las expresiones regulares, tenemos que estudiar las tres operaciones sobre los lenguajes que representan los operadores de las expresiones regulares. Estas operaciones son:  1. La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L, a M o a ambos.  Por ejemplo, si L = {001,10,111} y M = {ε,001}, entonces L ∪ M = {ε,10,001,111}. 2. La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar tomando cualquier cadena de L y concatenándola con cualquier cadena de M. Recuerde la Sección 1.5.2, donde definimos la concatenación de una pareja de cadenas; el resultado...
Publicar un comentario
Leer más