Siguiente: Producciones y Derivaciones
Subir: Conceptos básicos
Anterior: Palabras
Índice General
Un lenguaje es cualquier subconjunto del universo sobre
algún alfabeto, es decir,
, o también
.
Ejemplo:
- Lenguajes triviales
es el lenguaje vacio (que no contiene ninguna palabra),
-
es el lenguaje que solamente contiene la palabra vacio,
son independientes del alfabeto y por eso son lenguajes
sobre cualquier alfabeto.
- sea
-
-
es decir, el lenguaje que contiene
todas las palabras con un número de
s seguidos por el mismo número
de
s.
-
es decir, palíndromos
-
Si
para un lenguaje
, entonces se
llama
lenguaje finito.
Operaciones sobre/con lenguajes,
sean
lenguajes (igual para
):
- Unión:
-
Propiedades (unos ejemplos):
Conmutatividad: |
 |
Asociatividad: |
 |
Idempotencia: |
 |
Operación con : |
 |
Operación con
: |
 |
- Intersección:
-
Propiedades (unos ejemplos):
Conmutatividad: |
 |
Asociatividad: |
 |
Idempotencia: |
 |
Operación con : |
 |
Operación con
: |
 |
- Complemento:
-
Propiedades (unos ejemplos):
Regla de DeMorgan: |
 |
|
 |
Con estas tres operaciones la estructura
forma una álgebra booleana.
- Diferencia:
-
Propiedades (unos ejemplos):
- Concatenación:
-
Propiedades (unos ejemplos):
No-Conmutatividad: |
(en general) |
Operación con : |
 |
Operación con : |
 |
- Potencia:
-
Propiedades (unos ejemplos):
Cero-Potencia: |
 |
Inducción: |
 |
- Clausura positiva:
-
- Clausura (de Kleene):
-
Propiedades (unos ejemplos):
- Reflexión (o inverso):
-
- Homomorfismo:
- Sean
dos alfabetos.
Sea
una función
que asigna a cada símbolo de
una palabra sobre
.
Podemos ampliar la función
a un homomorfismo
, es decir, una función que asigna a cada
palabra sobre
una palabra sobre
, con
Ejemplo:
Entonces si
es un lenguaje sobre
es un lenguaje sobre
y
si
es un lenguaje sobre
, entonces
es un lenguaje sobre
.
¿Cuál es el orden de prioridad de estos operadores?
Siguiente: Producciones y Derivaciones
Subir: Conceptos básicos
Anterior: Palabras
Índice General
© 2006, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática