Exercício 06.04

Desenvolva uma Expressão Regular (ER) sobre o alfabeto Σ = {x, y, z} e o Autômato Finito com Movimentos Vazios (AFε) correspondente, pelo Algoritmo de Thompson, que reconheça a linguagem L = {w | w possui xyz como prefixo, zxy como subpalavra e xyx como sufixo}.


Expressão Regular (ER)

ER = (xyz(x + y + z)*zxy(x + y + z)*xyx) +

          (xyzxy(x + y + z)*xyx) +

          (xyz(x + y + z)*zxyx) +

          (xyzxyx)


Expressão Regular (ER) Simplificada

ER = xyz(ε + (x + y + z)*z)(ε + xy(x + y + z)*)xyx


Autômato Finito com Movimentos Vazios (AFε)

M = ({x, y, z}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q25, q26, q27, q28, q29, q30, q31, q32, q33, q34, q35, q36, q37, q38, q39, q40, q41, q42, q43, q44}, δ, q0, {q44})

δ x y z ε
q0 - - - {q1}
q1 {q2} - - -
q2 - {q3} - -
q3 - - {q4} -
q4 - - - {q5}
q5 - - - {q6, q19}
q6 - - - {q7}
q7 - - - {q8, q16}
q8 - - - {q9}
q9 - {q14} - {q10, q12}
q10 {q13} - - -
q11 - - - {q14}
q12 - - {q13} -
q13 - - - {q14}
q14 - - - {q15}
q15 - - - {q8, q16}
q16 - - - {q17}
q17 - - {q18} -
q18 - - - {q21}
q19 - - - {q20}
q20 - - - {q21}
q21 - - - {q22}
q22 - - - {q23, q37}
q23 {q24} - - -
q24 - {q25} - -
q25 - - - {q26}
q26 - - - {q27, q35}
q27 - - - {q28}
q28 - {q33} - {q29, q31}
q29 {q30} - - -
q30 - - - {q33}
q31 - - {q32} -
q32 - - - {q33}
q33 - - - {q34}
q34 - - - {q27, q35}
q35 - - - {q36}
q36 - - - {q39}
q37 - - - {q38}
q38 - - - {q39}
q39 - - - {q40}
q40 {q41} - - -
q41 - {q42} - -
q42 {q43} - - -
q43 - - - {q44}
q44 - - - -

Recomendamos

Revista FOSSGIS Brasil Vida de Suporte Vida de Programador