Teoria De La Computacion Ejercicios 2.9-2.10-2.12

Universidad Nacional de Colombia
Facultad de Ingeniería – Teoría de la Computación


Ejercicios Sección 2,9:

1.
2.3.

Ejercicios Sección 2,10:

1.
i. X=(a∪b)X∪{λ}A=(a∪b)B={λ}PorellemadeArden:X=(a∪b)*{λ}=(a∪b)*

ii.X=aX∪bX∪b*ab∪a*=(a∪b)X∪(b*ab∪a*)A=(a∪b)B=(b*ab∪a*)PorellemadeArden:X=(a∪b)*(b*ab∪a*)

2.SiY=A*(B∪D)essolucióndeX=AX∪B,entonces:A*(B∪D)=A(A*(B∪D))∪B=A(A*B∪A*D)∪B=A+B∪A+D∪B=(A+∪λ)B∪A+DA*B∪A*D=A*B∪A+DParaquelaigualdadsecumpla,λdebeperteneceraA(λ∈A).ConestosedemuestraqueYdebeserigualaA*(B∪D)cuandoλ∈A.

Ejercicios Sección 2,12:

1.
i.A0=aA1∪bA2①A1=aA0∪bA3②A2=bA0∪aA3∪λ③A3=bA1∪aA2④Reemplazando④en②:A1=aA0∪b2A1∪abA2⑤Reemplazando④en③:A2=bA0∪abA1∪a2A2∪λ⑥AplicandoelL.A.en⑥:A2=(a2)*(bA0∪abA1∪λ)⑦Reemplazando⑦en①:A0=aA1∪b2(a2)*A0∪ab2(a2)*A1∪b(a2)*⑧Reemplazando⑦en⑤:A1=aA0∪b2A1∪ab2(a2)*A0∪a2b2(a2)*A1∪ab(a2)*⑨Ahoratenemoselsistema:A0=b2(a2)*A0∪[a∪ab2(a2)*]A1∪b(a2)*①A1=[a∪ab2(a2)*]A0∪[b2∪b2(a2)+]A1∪ab(a2)*②HaciendoP=[b2∪b2(a2)+]yS=b2(a2)*,①y②sepuedenescribircomo:A0=SA0∪[a∪aS]A1∪b(a2)*①A1=[a∪aS]A0∪PA1∪ab(a2)*②AplicandoelL.A.en②:A1=P*[(a∪Sa)A0∪ab(a2)*]③Reemplazando③en①:A0=SA0∪[a∪Sa][(P*a∪P*Sa)A0∪P*ab(a2)*]∪b(a2)*④AplicandoelL.A.en④:A0=[S∪(a∪Sa)(P*a∪P*Sa)]*[(a∪Sa)(P*ab(a2)*)∪b(a2)*]AlsustituirPySenlaecuaciónanteriorseobtienelaexpresiónregula

rparaL.ii....