¿Qué es un lenguaje?

Informalmente: un lenguaje es un conjunto de palabras o sentencias formadas sobre un alfabeto.

1.1 Alfabeto:

Definición (Alfabeto):

Conjunto finito, no vacío, de elementos.

Generalmente usaremos Σ para especificar alfabetos y los elementos los denominaremos “letras” o “símbolos”.

Ejemplos: Los alfabetos español, inglés, o alemán

Σ1={0,...,9}, 0 ∈Σ 1

Σ2={x | x es un símbolo del código ASCII}

Σ3={(, )}

Σ4={1, A, 2, B}

Σ5={a, b, c, d}

Σ6={}

Σ7=ℵ

Concepto de Lenguaje Formal

Definición (Palabra):

Sea un alfabeto Σ. Una palabra sobre Σ es una secuencia finita de las letras de ese alfabeto.

La secuencia vacía representa la palabra vacía y la anotamos con λ.

Ejemplos: sobre Σ5 ={a,b,c,d}: λ, a, b, c, d, abc, aab, dcba, ... sobre Σ1 ={0,...,9}: λ, 0, 0000, 010, 9980, ... sobre Σ3 ={(,)} λ, (, ), (), (()()), )())), ...