Sistemas Formales

Teoría de Autómatas y Lenguajes Formales Capítulo 2: “Lenguajes Formales”
Holger Billhardt holger.billhardt@urjc.es

Sumario:
Capítulo 2: “Lenguajes Formales”
1. 2.

Concepto de Lenguaje Formal Operaciones sobre Lenguajes Formales (u otros conjuntos)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

2

1Sumario:
Capítulo 2: “Lenguajes Formales”
1. 2.

Concepto de Lenguaje Formal Operaciones sobre Lenguajes Formales (u otros conjuntos)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

3

Concepto de Lenguaje Formal
¿Qué es un lenguaje?

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

Pasaremos a definirlo de manera formal.

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

4

2

Concepto de Lenguaje Formal
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=ℵ

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

5

Concepto de Lenguaje Formal
Palabras:
Definición (Palabra):
Sea un alfabeto Σ. Una palabra sobre Σ es unasecuencia 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 ={(,)} λ, (, ), (), (()()), )())), ...

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática deSistemas

6

3

Concepto de Lenguaje Formal
Palabras:
Definición (Longitud de una palabra):
Se llama longitud de una palabra x, y se representa por |x|, al número de símbolos que la componen. Ejemplos:
sobre Σ5 ={a,b,c,d}: |λ|=0, |a|=1, |abc|=3

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

7

Concepto de LenguajeFormal
Operaciones con palabras:
Definición (Concatenación):
Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda). Sean x=A1A2...An e y=B1B2...Bm con Ai, Bi ∈ Σ: ⇒ xy= A1A2...AnB1B2...Bm Ejemplos:
x =abc, y =da,definidos sobre Σ={a,b,c,d} xy=abcda ; |xy|=|x|+|y|=5

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

8

4

Concepto de Lenguaje Formal
Operaciones con palabras:
Propiedades de la concatenación:
Operación cerrada: sí Si x e y están definidos sobre Σ, entonces xy está definido sobre Σ. asociativa: sí
x(yz)=(xy)zElemento nulo: λ
xλ=λx=x

Conmutatividad: no
xy≠yx

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

9

Concepto de Lenguaje Formal
Operaciones con palabras:
Definición (Potencia):
Sea i un número natural, y x una palabra. La potencia i-ésima de x, denominada xi, es la operación que consiste en concatenarla consigomisma i veces.

Ejemplos:
x =abc ⇒ x1=abc x2=abcabc x3=abcabcabc

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

10

5

Concepto de Lenguaje Formal
Operaciones con palabras:
Propiedades de la potencia:
∀ i, j > 0 xi+1=xxi=xix xixj=xi+j
Se define x0=λ (palabra vacía): Si i=0 ⇒ x0+1=x1=x=xλ=xx0=λx=x0x Si i,j=0...