LENGUAJES Y AUTOMATAS 1: LENGUAJES

Un lenguaje

es un conjunto de cadenas sobre un alfabeto $\Sigma$ definido, éstas pueden ser cualquier cadena

, que cumpla con lo siguIente,

esta formada por los símbolos $\sigma_1\sigma_{2}\ldots\sigma_{k}$ donde $\sigma_k \in \Sigma\ \forall k$ .

El lenguaje vacío es aquel que no contiene cadenas y no es lo mismo que el lenguaje formado por la cadena vacía $\{\varepsilon\}$ , éste lenguaje se denota de la misma manera que el conjunto vacío, $\emptyset$ .
Sí se tiene una cadena

sobre un alfabeto $\Sigma$ y

es el lenguaje compuesto por algunas de las cadenas sobre el alfabeto $\Sigma$ y $w \in L$ , entonces diremos que

es un miembro de

.

Un lenguaje universal sobre algún alfabeto $\Sigma$ , o cerradura de $\Sigma$ , es el lenguaje que contiene todas las cadenas que es posible formar con los símbolos de $\Sigma$ y se denota como $\Sigma^*$ .

Ejemplo: Sea $\Sigma=\{a\}$ , entonces $\Sigma^*=\{\varepsilon,a,aa,aaa,\ldots\}.$
Podemos observar que para cualquier alfabeto $\Sigma$ , $\Sigma^*$ es infinito, ya que los alfabetos son conjuntos no vacíos.

LENGUAJES Y AUTOMATAS 1

miércoles, 31 de enero de 2018

LENGUAJES

No hay comentarios:

Publicar un comentario