Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) AFD e ≡ ⊆ Q 1 × Q 1 a relação em Q 1 definida por p ≡ q sse ∀ x ∈ Σ *( δ *(p, x ) ∈ A 1 ↔ δ *(q, x ) ∈ A 1 ). Seja M 2 = (Q 2 , Σ , q 2 , A 2 , δ 2 ) AFD, onde : Q 2 = {[q] ≡ | q ∈ Q 1 } q 2 = [q 1 ] ≡ δ 2 : Q 2 × Σ → Q 2 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ): δ 2 ([q] ≡ ,a) = [ δ 1 (q,a)] ≡ A 2 ={[q] ≡ | 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 uma prova da tese de indução ?

Question

Seja  M 1  = (Q 1 , Σ , q 1 , A 1 ,  δ 1 ) AFD e  ≡ ⊆ Q 1 × Q 1  a  relação  em Q 1 definida por  p ≡ q  sse ∀ x ∈ Σ *( δ *(p, x ) ∈ A 1 ↔  δ *(q, x ) ∈ A 1 ).  Seja  M 2  = (Q 2 , Σ , q 2 , A 2 ,  δ 2 ) AFD,  onde : Q 2  = {[q] ≡  | q ∈ Q 1 } q 2  = [q 1 ] ≡ δ 2 : Q 2 × Σ →  Q 2  ( ∀ q ∈ Q 1 ,  ∀ a ∈ Σ ): δ 2  ([q] ≡ ,a) = [ δ 1 (q,a)] ≡ A 2 ={[q] ≡ | 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 uma prova da tese de indução ?

Accepted Answer

δ 2 * (q 2 , xa )           =           δ 2 ( δ 2 * (q 2 ,x),a)              def.  δ *  AFD (ii)                         =           δ 2 ( [ δ 1 * (q 1 ,x)] ≡ ,a)           hipótese de indução                          =           [ δ 1 ( δ 1 * (q 1 ,x),a)] ≡           def.  δ 2  em M 2                         =          [ δ 1 * (q 1 , xa )] ≡                 def.  δ *  AFD (ii)

Answer

δ 2 * (q 2 , xa )           =           δ 2 ( δ 2 * (q 2 ,x),a)              def.  δ *  AFD (ii)                         =           δ 2 ( [ δ 1 * (q 1 ,x)] ≡ ,a)           hipótese de indução                          =           δ 1 ( δ 1 * (q 1 ,x),a)] ≡           def.  da relação de indistinguibilidade ≡                          =          [ δ 1 * (q 1 , xa )] ≡                 def.  δ *  AFD (ii)

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 , Λ )            =          q 2                                 def.  δ * AFD (i)                         =          [q 1 ] ≡                                      def. q 2   em M 2                              =          [ δ 1 * (q 1 , Λ )] ≡                        def.  δ * AFD (i)

Crowdly

Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) AFD e ≡ ⊆ Q 1 × Q 1 a relação em ...

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