1.1-Conceptos Básicos y Notación en Lenguajes y Autómatas

 

Tutorial: Conceptos Básicos y Notación en Lenguajes y Autómatas

1. ¿Qué es un Lenguaje Formal?

En teoría de lenguajes, un lenguaje formal NO es como el español o inglés. Es simplemente un conjunto de palabras construidas a partir de símbolos.

Ejemplo simple:

• Símbolos disponibles: {a, b}

• Algunas palabras posibles: "a", "b", "aa", "ab", "ba", "aaa", etc.

• Un lenguaje podría ser: {a, aa, aaa} (solo palabras con 'a's, máximo 3)

---

2. Conceptos Clave y Notación

a) Alfabeto (Σ)

• Definición: Conjunto finito de símbolos básicos

• Notación: Σ (sigma mayúscula)

• Ejemplos:

  • Σ = {0, 1} (alfabeto binario)

  • Σ = {a, b, c}

  • Σ = {↑, ↓, →, ←}

b) Cadena/Palabra (w)

• Definición: Secuencia finita de símbolos del alfabeto

• Ejemplo: Si Σ = {0, 1}

  • "0110" es una cadena

  • "101" es otra cadena

  • "" (cadena vacía) también es válida

c) Cadena Vacía (ε o λ)

• Notación: ε (épsilon) o λ (lambda)

• Es la cadena sin símbolos

• Importante: ¡Siempre es parte de las operaciones!

d) Longitud de una Cadena

• Notación: |w|

• Ejemplo: |"abc"| = 3, |ε| = 0

---

3. Operaciones Básicas con Cadenas

a) Concatenación

• Símbolo: · (o simplemente juntar)

• Ejemplo: "ab" · "cd" = "abcd"

• Propiedad: w · ε = ε · w = w

b) Potencia de una Cadena

• Notación: wⁿ

• Ejemplo: Si w = "ab":

  • w⁰ = ε

  • w¹ = "ab"

  • w² = "abab"

  • w³ = "ababab"

---

4. Lenguaje Formal (L)

Definición:

Un lenguaje L sobre un alfabeto Σ es cualquier subconjunto de Σ* (todas las cadenas posibles)

Notación Importante:

Símbolo	Significado
Σ*	Todas las cadenas posibles con Σ (incluye ε)
Σ⁺	Todas las cadenas NO vacías con Σ
∅	Lenguaje vacío (no tiene cadenas)
{ε}	Lenguaje que solo tiene la cadena vacía

Ejemplos:

1. L₁ = {a, aa, aaa} sobre Σ = {a}

2. L₂ = {w | w tiene igual número de 0 y 1} sobre Σ = {0, 1}

3. L₃ = ∅ (lenguaje sin palabras)

---

5. Operaciones con Lenguajes

a) Unión (L₁ ∪ L₂)

• Ejemplo: {a, ab} ∪ {b, ab} = {a, ab, b}

b) Intersección (L₁ ∩ L₂)

• Ejemplo: {a, ab} ∩ {b, ab} = {ab}

c) Concatenación (L₁ · L₂)

• Ejemplo: {a, b} · {c, d} = {ac, ad, bc, bd}

d) Estrella de Kleene (L*)

• Todas las concatenaciones posibles (0 o más veces)

• Ejemplo: Si L = {a}, entonces:

  • L* = {ε, a, aa, aaa, aaaa, ...}

---

6. Ejemplo Completo Paso a Paso

Problema: Trabajar con Σ = {x, y}

Paso 1: Crear algunas cadenas

• w₁ = "xy"

• w₂ = "yxx"

Paso 2: Calcular longitudes

• |w₁| = 2

• |w₂| = 3

Paso 3: Concatenar

• w₁ · w₂ = "xyyxx"

Paso 4: Definir un lenguaje

• L = {w | w empieza con 'x'} = {"x", "xy", "xx", "xyy", ...}

Paso 5: Aplicar estrella de Kleene

• Si M = {x}, entonces M* = {ε, x, xx, xxx, xxxx, ...}

---

7. Resumen Visual

text

Alfabeto Σ = {0, 1}
  ↓
Cadenas posibles: ε, 0, 1, 00, 01, 10, 11, 000, ...
  ↓
Elegimos un subconjunto = LENGUAJE
  ↓
Ejemplo: L = {w | w termina en 1} = {1, 01, 11, 001, 011, ...}

---

8. Ejercicio Práctico

Dado Σ = {a, b}, considera:

• L₁ = {a, aa}

• L₂ = {b, bb}

Calcula:

1. L₁ ∪ L₂ = ?

2. L₁ · L₂ = ?

3. |"aba"| = ?

4. ¿Pertenece "aaa" a L₁*?

Respuestas:

1. {a, aa, b, bb}

2. {ab, abb, aab, aabb}

3. 3

4. Sí, porque L₁* = {ε, a, aa, aaa, aaaa, ...}

---

Conclusión

Los lenguajes formales son solo conjuntos de palabras. La notación puede parecer abstracta al principio, pero sigue reglas matemáticas precisas. ¡Todo lo que viene después (autómatas, gramáticas) se construye sobre estos conceptos básicos!

Siguiente paso: Aprender cómo describir estos lenguajes usando expresiones regulares o cómo reconocerlos usando autómatas finitos