Exercício 06.02

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 xy como prefixo, yzx como subpalavra e xzx como sufixo}.


Expressão Regular (ER)

ER = (xy(x + y + z)*yzx(x + y + z)*xzx) +

          (xyzx(x + y + z)*xzx) +

          (xy(x + y + z)*yzxzx) +

          (xyzxzx)


Expressão Regular (ER) Simplificada

ER = xy(ε + (x + y + z)*y)z(ε + x(x + y + z)*)xzx


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, q18}
q5 - - - {q6}
q6 - - - {q7, q15}
q7 - - - {q8}
q8 - {q13} - {q9, q11}
q9 {q10} - - -
q10 - - - {q13}
q11 - - {q12} -
q12 - - - {q13}
q13 - - - {q14}
q14 - - - {q7, q15}
q15 - - - {q16}
q16 - {q17} - -
q17 - - - {q20}
q18 - - - {q19}
q19 - - - {q20}
q20 - - - {q21}
q21 - - {q22} -
q22 - - - {q23}
q23 - - - {q24, q37}
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

Java Magazine Revista Espírito Livre Agenda TI