Lenguajes Formales desde CERO

 Lenguajes Formales desde CERO

Introducción: Números y Palabras

¿Dónde se unen los números y las palabras? Un ejemplo claro es la propiedad espejo (palíndromos numéricos), donde un número se lee igual de izquierda a derecha que de derecha a izquierda. Para estudiar los números como palabras, necesitamos herramientas matemáticas: los lenguajes formales.

¿Qué veremos en este tutorial?

  • Qué son los lenguajes formales.

  • Operaciones básicas sobre ellos.

  • Su relación con la teoría de autómatas.

1. Alfabeto (Σ)

Un alfabeto es un conjunto finito de símbolos.

Ejemplos:

  • Alfabeto español: {a, b, c, ..., z}.

  • Alfabeto binario: {0, 1}.

  • Alfabeto decimal: {0, 1, 2, ..., 9}.

¡Importante!
Un alfabeto debe ser finito.
❌ Los números naturales no son un alfabeto (son infinitos).
✅ Los dígitos del 0 al 9 sí forman un alfabeto finito. Con combinaciones de estos símbolos podemos representar todos los números naturales.

2. Cadenas (o Palabras)

Una cadena es una secuencia finita y ordenada de símbolos de un alfabeto.

Ejemplo:

  • Con Σ = {a, b, c}, "abc" es una cadena válida.

  • Con Σ = {0, 1}, "0110" es una cadena válida.

Cadena vacía (λ o ε)

Es una cadena de longitud cero, sin símbolos. Es un concepto fundamental en lenguajes formales.

3. Propiedades de las Cadenas

Longitud de una cadena

La longitud (|w|) es el número de símbolos en la cadena.

Definición recursiva:

  • |λ| = 0.

  • Si w = a · x (donde 'a' es un símbolo y 'x' es una cadena), entonces |w| = 1 + |x|.

Ejemplo:
Para w = "like":

  • |"like"| = 1 + |"ike"|

  • |"ike"| = 1 + |"ke"|

  • |"ke"| = 1 + |"e"|

  • |"e"| = 1 + |λ| = 1 + 0 = 1

  • Resultado: |"like"| = 4.

Conteo de apariciones

|w|_a = número de veces que aparece el símbolo 'a' en la cadena w.

Ejemplo:
Para w = "suscrito", |w|_s = 2.

4. Orden de Cadenas

Para ordenar cadenas, primero se considera la longitud, luego el orden alfabético.

Ejemplos:

  • "hola" (longitud 4) va antes que "mundo" (longitud 5).

  • Si tienen igual longitud (ej: "sol" y "sal"): se ordenan alfabéticamente según los símbolos en cada posición ("sal" antes que "sol").

5. Conjunto de Todas las Cadenas Posibles

Alfabeto elevado a n (Σⁿ)

Conjunto de todas las cadenas de longitud n sobre Σ.

Ejemplo: Σ = {0, 1}

  • Σ⁰ = {λ} (solo cadena vacía)

  • Σ¹ = {0, 1}

  • Σ² = {00, 01, 10, 11}

  • Σⁿ tiene 2ⁿ elementos (combinatoria).

Clausura de Kleene (Σ*)

Es el conjunto de todas las cadenas posibles de cualquier longitud (incluida λ) sobre Σ.

Fórmula: Σ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ Σ³ ∪ ...

Ejemplo: Σ = {0, 1}
Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, 001, ...} (¡infinito!)

Clausura Positiva (Σ⁺)

Igual que Σ*, pero excluyendo la cadena vacía λ.
Σ⁺ = Σ¹ ∪ Σ² ∪ Σ³ ∪ ...

6. Aplicación y Significado

La Clausura de Kleene representa todas las posibilidades infinitas de un alfabeto:

Ejemplos:

  • Σ = {0, 1}: Σ* = todos los números binarios posibles.

  • Σ = letras español: Σ* = todas las palabras que puedan existir (pasado, presente y futuro).

  • Σ = caracteres ASCII: Σ* = todas las novelas, conversaciones, códigos, etc., escritos con ASCII.

Resumen de Conceptos Clave

TérminoDefiniciónSímbolo/Ejemplo
AlfabetoConjunto finito de símbolosΣ = {a, b, c}
CadenaSecuencia finita de símbolosw = "abc"
Cadena vacíaCadena de longitud 0λ o ε
LongitudNúmero de símbolos|"hola"| = 4
ΣⁿCadenas de longitud nΣ² = {aa, ab, ba, bb}
Σ* (Kleene)Todas las cadenas posibles (con λ)Σ* = Σ⁰ ∪ Σ¹ ∪ ...
Σ⁺ (Positiva)Todas las cadenas posibles (sin λ)Σ⁺ = Σ¹ ∪ Σ² ∪ ...

Próximos Pasos

En el siguiente tutorial veremos:

  • Operaciones con cadenas (concatenación, inversión, potencias).

  • Definición formal de lenguaje (subconjunto de Σ*).

  • Operaciones entre lenguajes (unión, intersección, concatenación).

¡No olvides practicar!
Prueba con diferentes alfabetos y genera ejemplos de cadenas, calcula longitudes, ordena cadenas y explora las infinitas posibilidades de Σ*.

Este es solo el comienzo del fascinante mundo de los lenguajes formales y su conexión con la teoría de autómatas. ¡Hasta el próximo tutorial!

Comentarios

Publicar un comentario

Entradas más populares de este blog

Lenguajes Formales en el Contexto de Autómatas

  Lenguajes Formales en el Contexto de Autómatas ¿Qué es un Lenguaje Formal? Un  lenguaje formal  es un conjunto de cadenas (palabras) construidas a partir de un alfabeto finito, usando reglas precisas y matemáticas. No se trata de "hablar formalmente", sino de definir  estructuras sintácticas  de manera rigurosa y matemática. Componentes Fundamentales 1. Alfabeto (Σ) Un conjunto  finito  de símbolos básicos. Ejemplo: Σ = {a, b, c} Ejemplo binario: Σ = {0, 1} 2. Cadena (palabra) Una secuencia finita de símbolos del alfabeto. Ejemplo: "abac", "00101", "ε" (cadena vacía) 3. Lenguaje (L) Un  conjunto  de cadenas sobre un alfabeto. Ejemplo: L = {ab, ba, aab} sobre Σ = {a, b} Ejemplo: L = {todas las cadenas con igual número de 0's y 1's} Operaciones con Lenguajes Unión (∪) L₁ ∪ L₂ = {w | w ∈ L₁  o  w ∈ L₂} Ejemplo: Si L₁ = {ab, ba} y L₂ = {aa, ab}, entonces: L₁ ∪ L₂ = {ab, ba, aa} Concatenación (∘ o simplemente juntar) L₁ ∘ L₂ = {xy | x ...
Leer más

Cada Símbolo Explicado ANTES de Usarlo

  Tutorial Super Detallado: Cada Símbolo Explicado ANTES de Usarlo ¡Perfecto! Vamos a explicar cada símbolo por separado antes de juntarlos, como presentar los ingredientes antes de cocinar. 📌 PRIMERO: Conoce Tus "Ingredientes" (Símbolos Básicos) 1. Σ (Sigma mayúscula) - Tu CAJA DE HERRAMIENTAS text Explicación: Es el conjunto de "piezas básicas" que vas a usar. Se pronuncia: "Sigma" Ejemplo visual: Σ = {😀, 😭, 🎮}  ← Tienes 3 emojis para trabajar Para alumnos: Imagina que Σ es tu mochila de colores. Si Σ = {🟥, 🟦}, solo puedes usar rojo y azul. 2. { } (Llaves) - La BOLSA donde guardas cosas text Explicación: Indica un CONJUNTO (grupo de cosas). Se lee: "el conjunto de..." Ejemplo: {A, B, C} significa "el conjunto que tiene A, B y C" Para alumnos: Las llaves son como un estuche: {lápiz, goma, sacapuntas} ← todo lo que hay dentro. 3. ε (épsilon) / λ (lambda) - La FIGURA INVISIBLE text Explicación: Representa la "cadena vacía...
Leer más

Por qué usar notación formal

  La notación matemática elimina ambigüedades y permite hacer demostraciones. Compara: Versión informal: “cadenas con número par de a’s” Versión formal:  L = { w ∈ { a , b } ∗ ∣ ∣ w ∣ a ≡ 0   ( mod  2 ) } L = { w ∈ { a , b } ∗ ∣ ∣ w ∣ a ​ ≡ 0   ( mod  2 )} La formalización aclara: Alfabeto:  { a , b } { a , b } Se incluye la cadena vacía (porque  Σ ∗ Σ ∗  la incluye). “Par” se define como congruente con 0 módulo 2. Solo importa el conteo de ‘a’, no importa el orden ni la cantidad de ‘b’. 6. En términos de autómatas Este lenguaje es reconocido por un  autómata finito determinista  con dos estados: Estado  q 0 q 0 ​  (par de a’s, estado inicial y final) Estado  q 1 q 1 ​  (impar de a’s, no final) Transiciones: Con ‘a’ cambias de estado. Con ‘b’ te quedas en el mismo estado. Resumen final L = { w ∈ Σ ∗ ∣ ∣ w ∣ a ≡ 0 ( m o d 2 ) } L = { w ∈ Σ ∗ ∣ ∣ w ∣ a ​ ≡ 0 ( mod 2 )} “L es el conjunto de todas las cadenas sobre {...
Leer más