Homework 7

Solving right-linear equations by Arden’s rule:

X=PXQ=PQX=PX\cup Q=P^*Q
  1. a

C=0C1A=01AC=0C\cup1A=0^*1A

B=0A0B1C=0A0B01A=0B0A01A=0(0A01A)B=0A\cup0B\cup1C\\ =0A\cup0B\cup0^*1A\\ =0B\cup0A\cup0^*1A\\ =0^*(0A\cup0^*1A)
A=0A1Bλ=0A10(0A01A)λ=0A100A1001Aλ=(01001001)Aλ=(01001001)A=0A\cup1B\cup\lambda\\ =0A\cup10^*(0A\cup0^*1A)\cup\lambda \\ =0A\cup10^*0A\cup10^*0^*1A\cup\lambda\\ =(0\cup10^*0\cup10^*0^*1)A\cup\lambda\\ =(0\cup10^*0\cup10^*0^*1)^*
  1. b

B=0D=0D=0DB=0D=\emptyset\cup0D=0D

D=1B1Cλ=10D1Cλ=(10)(1Cλ)D=1B\cup 1C \cup \lambda=10D\cup1C\cup\lambda=(10)^*(1C\cup\lambda)

C=0A=0A=0AC=0A=\emptyset\cup0A=0A

L(M2)=E(A)E(C)=0B1C0Aλ=00D10A0Aλ=00(10)(1Cλ)10Aλ=00(10)(10Aλ)10A0Aλ=00(10)10A00(10)10Aλ=(00(10)1010)A00(10)λ=(00(10)10100)00(10)L(M2)=E(A)\cup E(C)=0B\cup1C\cup0A \cup\lambda\\ =00D\cup10A\cup0A\cup \lambda\\ =00(10)^*(1C\cup\lambda)\cup10A\cup\lambda\\ =00(10)^*(10A\cup\lambda)\cup10A\cup0A\cup\lambda\\ =00(10)^*10A\cup00(10)^*\cup10A\cup\lambda\\ =(00(10)^*10\cup10)A\cup00(10)^*\cup\lambda\\ =(00(10)^*10\cup10\cup0)^*00(10)^*

  1. A
  1. B
  1. a

3. b

  1. a

4. b

  1. c