Baixe o app para aproveitar ainda mais
Prévia do material em texto
Autoˆmatos e Computabilidade – Teste 2 Construa um autoˆmato finito determin´ıstico que reconhec¸a a linguagem {w|w na˜o conte´m a subcadeia 110}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 q3 1 1 0 0 1 1,0 0 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1, q2} e δ : Q×Σ → Q e´ definida pela tabela 0 1 q0 q0 q1 q1 q0 q2 q2 q3 q2 q3 q3 q3 Construa um autoˆmato finito determin´ıstico que reconhec¸a a linguagem {w|w conte´m uma quan- tidade ı´mpar de 1s ou exatamente dois 0s}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 q3 q4 q5 q6 q7 0 0 0 0 0 0 0 0 11 11 11 11 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, . . . , q8}, F = {q2, q4, q5, q6, q7} e δ : Q× Σ → Q e´ definida pela tabela 0 1 q0 q1 q4 q1 q2 q5 q2 q3 q6 q3 q3 q7 q4 q5 q0 q5 q6 q1 q6 q7 q2 q7 q7 q3 Construa um autoˆmato finito determin´ıstico que reconhec¸a a linguagem {w|w conte´m pelo menos dois 1s e no ma´ximo dois 0s}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 1 1 1 1 1 1 1 1 1 1 1 0,1 0 0 0 0 0 0 0 0 0 0 0 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), ondeQ = {q0, q1, . . . , q11}, F = {q2, q5, q8} e δ : Q×Σ → Q e´ definida pela tabela 0 1 q0 q3 q1 q1 q4 q2 q2 q5 q2 q3 q6 q4 q4 q7 q5 q5 q8 q5 0 1 q6 q9 q7 q7 q10 q8 q8 q11 q8 q9 q9 q10 q10 q10 q11 q11 q11 q11 Construa um autoˆmato finito na˜o determin´ıstico que reconhec¸a a linguagem {w|w termina com 10}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 1 0 0,1 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2}, F = {q2} e δ : Q×Σε → P(Q) e´ definida pela tabela 0 1 ε q0 {q0} {q0, q1} ∅ q1 {q2} ∅ ∅ q2 ∅ ∅ ∅ Construa um autoˆmato finito na˜o determin´ıstico que reconhec¸a a linguagem {w|w comec¸a com 1s ou termina com 0s}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 q3 q4 ε 1 0,1 ε 0 0,1 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4}, F = {q2, q4} e δ : Q×Σε → P(Q) e´ definida pela tabela 0 1 ε q0 ∅ ∅ {q1, q3} q1 ∅ {q2} ∅ q2 {q2} {q2} ∅ q3 {q3} {q3} ∅ q4 ∅ ∅ ∅ Construa um autoˆmato finito na˜o determin´ıstico que reconhec¸a a linguagem {w|w conte´m pelo menos dois 1s e no ma´ximo dois 0s}, sobre o alfabeto {0, 1}. Fornec¸a o diagrama de estado do autoˆmato e tambe´m a descric¸a˜o formal do mesmo como uma 5-upla (Q,Σ, δ, q0, F ). Resposta: q0 q1 q2 q3 q4 q5 q6 q7 q8 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, . . . , q8}, F = {q2, q5, q8} e δ : Q × Σtexttt” → P(Q) e´ definida pela tabela 0 1 ε q0 {q3} {q1} ∅ q1 {q4} {q2} ∅ q2 {q5} {q2} ∅ q3 {q6} {q4} ∅ q4 {q7} {q5} ∅ 0 1 ε q5 {q8} {q5} ∅ q6 ∅ {q7} ∅ q7 ∅ {q8} ∅ q8 ∅ {q8} ∅
Compartilhar