03. Autômatos Finitos Não-Determinísticos (AFN)

Exercícios Propostos

Exercício 03.01 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui acc como prefixo, cba ou cac como subpalavra e acb como sufixo}.

Exercício 03.02 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3}, que reconheça a linguagem L = {w | w possui 132 ou 223 como prefixo, 232 ou 312 como subpalavra e 121 ou 321 como sufixo}.

Exercício 03.03 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui bac ou cbc como prefixo, bca ou caa como subpalavra e abc ou cac como sufixo}.

Exercício 03.04 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui acb ou cac como prefixo, baa ou cba como subpalavra e acb ou bac como sufixo}.

Exercício 03.05 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui abc ou cac como prefixo, cbb ou bcb como subpalavra e cba ou baa como sufixo}.

Exercício 03.06 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui bbc ou acc como prefixo, cab ou bcb como subpalavra e bba ou abc como sufixo}.

Exercício 03.07 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xxy ou yyz como prefixo, yxz ou yzx como subpalavra e xzz ou xyx como sufixo}.

Exercício 03.08 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui xyw ou wzz como prefixo, wzx ou wyx como subpalavra e xyy ou xwz como sufixo}.

Exercício 03.09 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui xyw ou wzw como prefixo, wzx ou ywx como subpalavra e xyy ou xwz como sufixo}.

Exercício 03.10 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xyz ou zyx ou yzy como prefixo, xyy ou xzx ou xxz como subpalavra e yxy ou yzy ou yxx como sufixo}.

Exercício 03.11 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abc ou bcd ou cdd como prefixo, dba ou cda ou cab como subpalavra e adb ou dad ou bca como sufixo}.

Exercício 03.12 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui bab ou dac ou ba como prefixo, abb ou cac ou acbc como subpalavra e bca ou acd ou cda como sufixo}.

Exercício 03.13 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui ab ou bcda ou bca como prefixo, dab ou acab ou cad como subpalavra e dad ou aba ou bbc como sufixo}.

Exercício 03.14 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iik ou kji ou jkj como prefixo, kjji ou jiik ou ikki como subpalavra e ikk ou jii ou kkj como sufixo}.

Exercício 03.15 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui xzxy ou wyzy ou zyyw como prefixo, ywzy ou wxxy ou xyx como subpalavra e xwzw ou yxx ou zw como sufixo}.

Exercício 03.16 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui accb ou cbab ou dacd como prefixo, bcad ou dcbd ou abca como subpalavra e adab ou abab ou dcab como sufixo}.

Exercício 03.17 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abab ou acdb ou bbac como prefixo, accba ou abccb ou badad como subpalavra e adc ou bab ou cbb como sufixo}.

Exercício 03.18 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abcd ou dcba ou baba como prefixo, badcd ou abcbc ou ccdab como subpalavra e bcca ou cdac ou dabc como sufixo}.

Exercício 03.19 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1234 ou 1212 ou 3434 como prefixo, 3412 ou 4421 ou 1243 ou 2234 como subpalavra e 2212 ou 1123 ou 2431 ou 3444 como sufixo}.

Exercício 03.20 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui abc ou cba como prefixo, acc ou abb como subpalavra e cbb ou caa como sufixo, caso a subpalavra seja acc, ou bab ou bcb como sufixo, caso a subpalavra seja abb}.

Exercício 03.21 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1332 ou 3212 ou 4134 como prefixo, 2314 ou 4324 ou 1231 como subpalavra e 1412 ou 1212 ou 4312 como sufixo}.

Exercício 03.22 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui xyxy ou xzwy ou yyxz como prefixo, xzzyx ou xyzzy ou yxwxw como subpalavra e xwz ou yxy ou zyy como sufixo}.

Exercício 03.23 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3}, que reconheça a linguagem L = {w | w possui 222 ou 322 como prefixo, 221 ou 222 como subpalavra e 211 ou 223 como sufixo}.

Exercício 03.24 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {w, x, y, z}, que reconheça a linguagem L = {w | w possui wzw ou zxy como prefixo, wxyw ou wzwx como subpalavra e wxw ou ywz como sufixo}.

Exercício 03.25 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui acb ou bca ou cac como prefixo, bab ou bba ou bcc como subpalavra e cac ou cbb ou cbc como sufixo}.

Exercício 03.26 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1241 ou 2443 ou 4323 como prefixo, 1431 ou 2342 ou 3421 como subpalavra e 1423 ou 2123 ou 2323 como sufixo}.

Exercício 03.27 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {w, x, y, z}, que reconheça a linguagem L = {w | w possui wxwx ou yzwx ou yzyz como prefixo, wxyz ou xxzy ou yzxw ou zzwx como subpalavra e wxxx ou xzwy ou yyzw ou zzyz como sufixo}.

Exercício 03.28 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 2113 ou 3121 ou 4241 como prefixo, 1321 ou 3441 ou 414 como subpalavra e 144 ou 23 ou 4323 como sufixo}.

Exercício 03.29 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui jki como prefixo, kikj como subpalavra e jki como sufixo}.

Exercício 03.30 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {w, x, y, z}, que reconheça a linguagem L = {w | w possui wzw ou ywz ou yzx como prefixo, xzx ou zww ou zxwx como subpalavra e wxz ou xyz ou zxy como sufixo}.

Exercício 03.31 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui jji ou kij como prefixo, ikj ou jij como subpalavra e ijk ou kjk como sufixo}.

Exercício 03.32 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3}, que reconheça a linguagem L = {w | w possui 121 ou 132 como prefixo, 123 ou 213 como subpalavra e 232 ou 332 como sufixo}.

Exercício 03.33 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abab ou acdb ou bbac como prefixo, abccb ou accba ou badad como subpalavra e adc ou bab ou cbb como sufixo}.

Exercício 03.34 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iki ou kji como prefixo, ijj ou kij como subpalavra e iji ou jki como sufixo}.

Exercício 03.35 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1212 ou 1234 ou 3434 como prefixo, 1243 ou 2234 ou 3412 ou 4421 como subpalavra e 1123 ou 2212 ou 2431 ou 3444 como sufixo}.

Exercício 03.36 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui cac ou dad como prefixo, cdb ou dcb como subpalavra e bdc ou dba como sufixo}.

Exercício 03.37 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 23 ou 3412 ou 342 como prefixo, 123 ou 2423 ou 421 como subpalavra e 121 ou 232 ou 334 como sufixo}.

Exercício 03.38 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui kij ou kjk como prefixo, jki ou kji como subpalavra e iij ou jij como sufixo}.

Exercício 03.39 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 124 ou 323 ou 432 como prefixo, 233 ou 2434 ou 424 como subpalavra e 241 ou 342 ou 412 como sufixo}.

Exercício 03.40 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 234 ou 341 ou 411 como prefixo, 132 ou 412 ou 423 como subpalavra e 121 ou 213 ou 342 como sufixo}.

Exercício 03.41 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iik ou jkj ou kji como prefixo, ikki ou jiik ou kjji como subpalavra e ikk ou jii ou kkj como sufixo}.

Exercício 03.42 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 2334 ou 3241 ou 4211 como prefixo, 1312 ou 4122 ou 4243 como subpalavra e 1231 ou 2123 ou 3442 como sufixo}.

Exercício 03.43 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3}, que reconheça a linguagem L = {w | w possui 132 ou 322 como prefixo, 223 ou 233 como subpalavra e 312 ou 331 como sufixo}.

Exercício 03.44 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 3243 ou 4413 como prefixo, 1314 ou 3243 como subpalavra e 4131 ou 4332 como sufixo}.

Exercício 03.45 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {w, x, y, z}, que reconheça a linguagem L = {w | w possui wxy ou xyy ou zwx como prefixo, xyz ou xzw ou ywz como subpalavra e wxz ou zyw ou yzy como sufixo}.

Exercício 03.46 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1142 ou 4141 ou 4231 como prefixo, 14343 ou 41221 ou 42214 como subpalavra e 141 ou 211 ou 432 como sufixo}.

Exercício 03.47 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xyx ou yxz ou zzy como prefixo, xzzy ou yxxz ou zyyz como subpalavra e xzz ou yyx ou zyy como sufixo}.

Exercício 03.48 Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui bcbc ou dabc ou dada como prefixo, aabc ou bcda ou ccad ou dacb como subpalavra e aada ou acbd ou bccc ou ddab como sufixo}.