Automatas

UNIVERSIDAD EAN
FACULTAD INGENIERIA
AUTOMATAS Y COMPILADORES
JOHANNA ANDREA ROJAS
COD: 200710705
15 DE OCTUBRE DE 2010
BOGOTA D.C

TAREA # 1

CAPÍTULO 1. SECCIÓN 1.5 [Hop2002]1) Sea el alfabeto Σ = {a,b,c,d,e}. Sean u = bcbaadb y v = ceec cadenas sobre Σ*.

Para cada uno de los ítems siguientes, desarrolle la operación, y además, escriba el nombre de laoperación desarrollada.

✓ u·v

RTA: Esta operacion es la concatenación de cadenzas , su desarrollo es:

u·v = {bcbaadbceec}

✓ |u|

RTA: Esta operacion se denomina, longitudde de una cadena,su desarrollo es:

|u| = 7

RTA: Esta operacion se denomina, potencia de una cadena,su desarrollo es:
✓ v3

v3 = {ceec ceec ceec}

RTA: Esta operacion sedenomina, reflexion de una cadena,su desarrollo es:

✓ vR

vR = {ceec}

2) Sean Σ = {a,b,c,d} y u = bcbaadb. Escriba todos los prefijos y sufijos de la cadena u.

RTA:

Prefijopropios de la cadena u:

{a, ab,abc}

Sufijos propios de la cadena u:

{d, cd,bcd}

3) Si

o W ∈ Σ*
o n,m ∈ ℕ

Demuestre que:

|wn+m| = |wn| + |wm|

RTA:Teniendo en cuenta, que la potencia de una cadena se define como wn donde wn = w.w.w.w n veces y que longitud de una cadena W ∈ Σ* se define como el numero de simbolos de W contando lossimbolos repetidos. Entonces si: W ∈ Σ* y n,m ∈ ℕ se demuestra que |wn+m| = |wn| + |wm|, porque:

Afirmacion 1: wn+m donde n+m = L, es decir: wL es igual a: w L veces , o sea que |W| =a1*a2*…* aL segun la longitud de una cadena, que es el resultado de concatenar.

Afirmacion 2: wn = w n veces + wm= w m veces = w n veces + w m veces, es decir: w Lveces, o sea que W = a1*a2*…* aL segun la longitud de una cadena, que es el resultado de concatenar.

Por lo tanto las dos afirmacion son equivalentes, es decir que: |wn+m| = |wn| + |wm|