Logica

Notas de Inducci´n (2)
o
Patricia Peratto
Abril 2013

1

Lenguajes formales (inductivos)

Para definir un lenguaje formal o inductivo, primero definimos un alfabeto, que es
un conjunto finito de s´
ımbolos (d´
ıgitos o letras).
Pensemos por ejemplo en el lenguaje natural (en nuestro caso el espa˜ ol).
n
Tenemos un alfabeto (abecedario) que utilizamos para construir las palabras dellenguaje. Las palabras son combinaciones de letras del alfabeto, pero no todas las
posibles combinaciones lo son.
En los lenguajes formales pasa lo mismo. Definimos un alfabeto y luego definimos el lenguaje cuyas palabras son combinaciones de letras del alfabeto.
Sin embargo tambi´n consideraremos el caso en el cual tenemos un lenguaje
e
formado por todas las posibles palabras que podemos formarcon un alfabeto.

Ejemplo 1.1. Alfabetos:
1. Σ = {a}.
2. Γ = {a, b, c}.
3. A = {1, 2, 3, 4}.
4. B = {a, b, 3, 4}.

1.1

Lenguajes particulares

Dado un alfabeto Σ, definimos un conjunto particular que denotamos con Σ∗ (y que
llamamos clausura de Σ) que es el conjunto de todas las palabras que se pueden
formar con las letras en Σ. Adem´s en Σ∗ tenemos una palabra particular que
allamamos palabra vacia que denotamos con ϵ.
Cuando formamos palabras, aplicamos una operaci´n particular que denotamos
o
concatenaci´n (juxtaposici´n) que consiste en agregar una letra o m´s a una palabra,
o
o
a
o juntar palabras. Por ejemplo, en la regla:
w ∈ L → abcw ∈ L
abcw es la palabra formada agregando abc adelante de w.
Las palabras en Σ∗ son las que podemos formar juxtaponiendo,en cualquier
orden, letras del alfabeto.
Definimos Σ+ = Σ∗ − {ϵ}, o sea que Σ+ es el mismo conjunto que Σ∗ excepto
que no tiene la palabra vacia.
1

Ejemplo 1.2. Si consideramos los alfabetos anteriores, tenemos que las siguientes
palabras pertenecen a la clausura:
Alfabeto: Σ = {a}.
palabras: a, aaaa, ϵ.
Alfabeto: Γ = {a, b, c}.
Palabras: abc, cba, ab, bba, a, b, c.
Alfabeto: A = {1,2, 3, 4}.
Palabras: 124, 241, 3124, 2, 31, ϵ.
Alfabeto: B = {a, b, 3, 4}.
Palabras: 34a, 3b4, 34, ab, 3b, 4a.

Cuando definimos un lenguaje inductivo, diferente de la clausura (o sea que hay
palabras en Σ∗ que no est´n en el lenguaje), nos tenemos que fijar que condiciones
a
cumplen las palabras del lenguaje para luego definir las cl´usulas. En este caso, si
a
el alfabeto es Σ, nuestroslenguajes son subconjuntos de Σ∗ .
Tenemos que tratar de no confundir el alfabeto con el lenguaje. Los elementos
del alfabeto pueden o no estar en el lenguaje y para que lo est´n tenemos que
e
especificarlo en la definici´n del mismo.
o
Ejemplo 1.3. Consideremos el alfabeto Γ = {a, b, c}.
Consideremos el lenguaje L1 ⊆ Γ∗ definido por las reglas:
i) ϵ ∈ L1
ii) a ∈ L1
iii) x ∈ L1, y ∈ L1 → axbyc∈ L1
En este caso, la palabra a pertenece a lenguaje, esto es asi pues hay una cl´usula
a
base ([ii)]) que dice eso y no porque a ∈ Γ.

Ejemplo 1.4. Otro ejemplo, es:
i) ϵ ∈ L2
ii) x ∈ L2 → ax ∈ L2
En este caso tenemos que podemos decir que a ∈ L2 (si sustituimos x por ϵ en
ii) obtenemos la palabra a).
En general, si no es especificado por una cl´usula o construido aplicando las
aclausulas del lenguaje, los elementos en el alfabeto no pertenecen al lenguaje.
2

Ejemplo 1.5. Ejemplos de lenguajes inductivos.
Abajo describimos propiedades que definen lenguajes y definiciones inductivas
que satisfacen las propiedades. Explicamos porqu´ las definiciones satisfacen las
e
propiedades.
1. {a}∗ es el conjunto de palabras formado por cualquier n´mero de letras a
u
incluyendo ϵ.Su definici´n inductiva es:
o
1) ϵ ∈ {a}∗
2) x ∈ {a}∗ → ax ∈ {a}∗

Consideremos las palabras del lenguaje en el orden en el cu´l se construyen.
a
Comenzamos siempre por las cl´usulas base (en este caso ϵ), entonces tena
emos que ϵ ∈ {a}∗ . Una vez hemos aplicado las cl´usulas base aplicamos
a
las clausulas inductivas (para hacer esto ultimo, sustituimos la (o las) vari´
´
ables por...