Seja M 1 = (Q 1 , Σ , q 1 , A 1 , δ 1 ) e M 2 = (Q 2 , Σ , q 2 , A 2 , δ 2 ) AFDs . Seja M = (Q, Σ , q 0 , A, δ ) AFD, onde : Q = Q 1 × Q 2 q 0 = (q 1 ,q 2 ) A={(p,q) | p ∈ A 1 Ú q ∈ A 2 } δ : Q 1 × Q 2 × Σ → Q 1 × Q 2 ( ∀ p ∈ Q 1 , ∀ q ∈ Q 2 , ∀ a ∈ Σ ): δ ((p,q),a) = ( δ 1 (p,a), δ 2 (q,a)). Na prova por indução estrutural de ∀ x ∈ Σ * δ *((p,q),x) = ( δ 1 *(p,x), δ 2 *(q,x)), qual das seguintes opções apresenta corretamente uma prova de L(M) = L(M 1 ) È L(M 2 ) ?

Question

Seja  M 1  = (Q 1 , Σ , q 1 , A 1 ,  δ 1 ) e M 2  = (Q 2 , Σ , q 2 , A 2 ,  δ 2 )  AFDs .  Seja  M = (Q, Σ , q 0 , A,  δ ) AFD,  onde : Q = Q 1 × Q 2 q 0  = (q 1 ,q 2 ) A={(p,q) | p ∈ A 1 Ú  q ∈ A 2 } δ : Q 1 × Q 2 × Σ →  Q 1 × Q 2  ( ∀ p ∈ Q 1 ,  ∀ q ∈ Q 2 ,  ∀ a ∈ Σ ): δ ((p,q),a) = ( δ 1 (p,a), δ 2 (q,a)). Na  prova por indução estrutural de ∀ x ∈ Σ *  δ *((p,q),x) = ( δ 1 *(p,x),  δ 2 *(q,x)), qual das seguintes opções apresenta corretamente uma prova de  L(M) = L(M 1 )  È  L(M 2 ) ?

Accepted Answer

x ∈ L(M)                                              hipótese  δ * (q 0 ,x) ∈ A                                         def. L(M) AFD δ * ((q 1 ,q 2 ),x) ∈ A                                  def. q 0  em M (δ 1 * (q 1 ,x), δ 2 * (q 2 ,x)) ∈ A                       ∀ x ∈ Σ *  δ *((p,q),x) = ( δ 1 *(p,x),  δ 2 *(q,x)) δ 1 * (q 1 ,x) ∈ A 1 Ú δ 2 * (q 2 ,x)) ∈ A 2              def. A em M x ∈ L(M 1 )  Ú  x ∈ L(M 2 )                          2x def. L(M) AFD x ∈ L(M 1 ) È L(M 2 )                               def.  È

Answer

x Î L(M)                                              hipótese  d * (q 0 ,x) Î A                                         def. L(M) AFD d * ((q 1 ,q 2 ),x) Î A                                  def. q 0  em M (d 1 * (q 1 ,x),  d 2 * (q 2 ,x)) Î A                       " x Î S *  d *((p,q),x) = ( d 1 *(p,x),  d 2 *(q,x)) d 1 * (q 1 ,x) Î A 1 Ù d 2 * (q 2 ,x)) Î A 2              def. A em M x Î L(M 1 )  Ù  x Î L(M 2 )                          2x def. L(M) AFD x Î L(M 1 ) Ç L(M 2 )                              def.  Ç

Answer

x Î L(M)                                              hipótese  d * (q 0 ,x) Î A                                         def. L(M) AFD d * ((q 1 ,q 2 ),x) Î A                                  def. q 0  em M (d 1 * (q 1 ,x),  d 2 * (q 2 ,x)) Î A                      def.  d  em M d 1 * (q 1 ,x) Î A 1 Ú d 2 * (q 2 ,x)) Î A 2              def. A em M x Î L(M 1 )  Ú  x Î L(M 2 )                          2x def. L(M) AFD x Î L(M 1 ) È L(M 2 )                              def.  È

Answer

x Î L(M)                                              hipótese  d * (q 0 ,x) Î A                                         def. L(M) AFD d * ((q 1 ,q 2 ),x) Î A                                  def. q 0  em M (d 1 * (q 1 ,x),  d 2 * (q 2 ,x)) Î A                       " x Î S *  d *((p,q),x) = ( d 1 *(p,x),  d 2 *(q,x)) d 1 * (q 1 ,x) Î A 1 Ù d 2 * (q 2 ,x)) Ï A 2              def. A em M x Î L(M 1 )  Ù  x Ï L(M 2 )                          2x def. L(M) AFD x Î L(M 1 ) –  L(M 2 )                               def.  –

Crowdly

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

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