Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) AFND - Λ . Seja M 2 = (Q 2 , Σ , q 2 , A 2 , δ 2 ) AFND, onde : Q 2 = Q 1 q 2 = q 1 δ 2 : Q 2 × Σ → Q 2 ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ): δ 2 (q,a) = δ 1 *(q,a) A 2 = A 1 ∪ {q 1 } , se Λ ({q 1 }) ∩ A 1 ≠ ∅ ; A 2 = A 1 , se Λ ({q 1 }) ∩ A 1 = ∅ . Na prova por indução estrutural de ∀ x ∈ Σ *–{ Λ } δ 2 *(q,x) = δ 1 *(q,x), qual das seguintes opções apresenta corretamente uma prova da tese de indução ?

Question

Seja  M 1  = (Q 1 , Σ , q 1 , A 1 ,  δ 1 ) AFND - Λ .  Seja  M 2  = (Q 2 , Σ , q 2 , A 2 ,  δ 2 ) AFND,  onde : Q 2  = Q 1 q 2  = q 1 δ 2 : Q 2 × Σ →  Q 2  ( ∀ q ∈ Q 2 ,  ∀ a ∈ Σ ): δ 2  (q,a) =  δ 1 *(q,a) A 2 = A 1 ∪ {q 1 }  ,  se Λ ({q 1 }) ∩ A 1 ≠ ∅ ; A 2 = A 1   ,  se Λ ({q 1 }) ∩ A 1 = ∅ . Na  prova por indução estrutural de ∀ x ∈ Σ *–{ Λ }  δ 2 *(q,x) =  δ 1 *(q,x),  qual das seguintes opções apresenta corretamente uma prova da tese de indução ?

Answer

δ 2 *(q, xa )             =           ∪ r ∈ δ 2*(q,x)  δ 2 (r,a)                                def.  δ *  AFND- Λ  (ii)                         =           ∪ r ∈ δ 1*(q,x)  δ 1 (r,a)                                  hipótese de indução                         =           δ 1 *(q, xa )                                            def.  δ *  AFND- Λ  (ii)

Answer

δ 2 *(q, xa )            =           ∪ r ∈ δ 2*(q,x)  δ 2 (r,a)                                 def.  δ *  AFND- Λ  (ii)                         =           ∪ r ∈ δ 1*(q,x)  δ 2 (r,a)                                 hipótese de indução                         =           ∪ r ∈ δ 1*(q,x)  δ 1 *(r,a)                               def.  δ 2  em M 2                         =           ∪ r ∈ δ 1*(q,x)  Λ ( ∪ t ∈ δ 1*(r, Λ )  δ 1 (t,a))          def.  δ *  AFND- Λ  (ii)                         =           ∪ r ∈ δ 1*(q,x)  Λ ( ∪ t ∈ Λ ({r})  δ 1 (t,a))            def.  δ *  AFND- Λ  (i)                         =           Λ ( ∪ r ∈ δ 1*(q,x)  ∪ t ∈ Λ ({r})  δ 1 (t,a))             Λ (A) ∪ Λ (B) =  Λ (A ∪ B)                         =           Λ ( ∪ r ∈ δ 1*(q,x)   δ 1 (r,a))                            Λ ({r})  ⊆ δ 1 *(q,x)                         =           δ 1 *(q, xa )                                             def.  δ *  AFND (ii)

Answer

δ 2 *(q, xa )           =           ∪ r ∈ δ 2*(q,x)  δ 2 (r,a)                                def.  δ *  AFND (ii)                         =           ∪ r ∈ δ 1*(q,x)  δ 2 (r,a)                                 hipótese de indução                         =           ∪ r ∈ δ 1*(q,x)  δ 1 *(r,a)                               def.  δ 2  em M 2                         =           ∪ r ∈ δ 1*(q,x)  Λ ( ∪ t ∈ δ 1*(r, Λ )  δ 1 (t,a))          def.  δ *  AFND- Λ  (ii)                         =           ∪ r ∈ δ 1*(q,x)  Λ ( ∪ t ∈ Λ ({r})  δ 1 (t,a))            def.  δ *  AFND- Λ  (i)                         =           Λ ( ∪ r ∈ δ 1*(q,x)  ∪ t ∈ Λ ({r})  δ 1 (t,a))             Λ (A) ∪ Λ (B) =  Λ (A ∪ B)                         =           Λ ( ∪ r ∈ δ 1*(q,x)   δ 1 (r,a))                           Λ ({r})  ⊆ δ 1 *(q,x)                         =           δ 1 *(q, xa )                                             def.  δ *  AFND- Λ  (ii)

Answer

δ 2 *(q, xa )           =           ∪ r ∈ δ 2*(q,x)  δ 2 (r,a)                                def.  δ *  AFND (ii)                        =           ∪ r ∈ δ 1*(q,x)  δ 1 (r,a)                                  hipótese de indução                        =           δ 1 *(q, xa )                                            def.  δ *  AFND (ii)

Crowdly

Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) AFND - Λ . Seja M 2 = (Q 2 , Σ , q...

Want instant access to all verified answers on moodle25.iscte-iul.pt?