Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) AFND. Seja M 2 = (Q 2 , Σ , q 2 , A 2 , δ 2 ) AFD, onde : Q 2 = 2 Q1 q 2 = {q 1 } δ 2 : Q 2 × Σ → Q 2 ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ): δ 2 (q,a) = ∪ r ∈ q δ 1 (r,a) A 2 ={q ∈ Q 2 | q ∩ A 1 ≠ ∅ } Na prova por indução estrutural de ∀ x ∈ Σ * δ 2 *(q 2 ,x) = δ 1 *(q 1 ,x), qual das seguintes opções apresenta corretamente u ma prova da base 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 ) AFD,  onde : Q 2  = 2 Q1 q 2  = {q 1 } δ 2 : Q 2 × Σ →  Q 2  ( ∀ q ∈ Q 2 ,  ∀ a ∈ Σ ): δ 2  (q,a) =  ∪ r ∈ q δ 1 (r,a) A 2 ={q ∈ Q 2  | q ∩ A 1 ≠ ∅ } Na  prova por indução estrutural de ∀ x ∈ Σ *  δ 2 *(q 2 ,x) =  δ 1 *(q 1 ,x),  qual das seguintes opções apresenta corretamente u ma prova da base  de indução ?

Answer

δ 2 *(q 2 , Λ )         =          q 2                                 def.  δ *  AFND (i)                         =          {q 1 }                            def. q 2  em M 2                          =           δ 1 *(q 1 , Λ )                     def.  δ *  AFD (i)

Answer

δ 2 *(q 2 , Λ )         =          q 2                                 def.  δ *  AFD (i)                         =          {q 1 }                            def. q 2  em M 2                          =           δ 1 *(q 1 , Λ )                     def.  δ *  AFND (i)

Answer

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

Answer

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

Crowdly

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

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