06. Conversão de Expressões Regulares (ER) para Autômatos Finitos Determinísticos (AFD)

pdfSlides


Exercícios Propostos

onExercício 06.01 Desenvolva uma Expressão Regular (ER) sobre o alfabeto Σ = {a, b, c} e o Autômato Finito com Movimentos Vazios (AFε) correspondente, pelo Algoritmo de Thompson, que reconheça a linguagem L = {w | w possui ab como prefixo, bca como subpalavra e aca como sufixo}.

onExercí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}.

offExercício 06.03 Desenvolva uma Expressão Regular (ER) sobre o alfabeto Σ = {a, b, c} e o Autômato Finito com Movimentos Vazios (AFε) correspondente, pelo Algoritmo de Thompson, que reconheça a linguagem L = {w | w possui cba como prefixo, aba como subpalavra e abc como sufixo}.

onExercí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}.

onExercício 06.05 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a(ab)*b. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados (Ricarte, 2008).

onExercício 06.06 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (xx)*(y + z)z*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados (Ricarte, 2008).

onExercício 06.07 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a*(b + c)c*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.08 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a(b + c)*b*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.09 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a + b)c*(b + a). Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.10 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a(b)*(b + c)*bc. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.11 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (ab)*(ba)*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

offExercício 06.12 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão ab(ε + (a + b)*b)a(ε + b(a + b)*)bb. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

offExercício 06.13 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão cba(ε + (a + b + c)*a)b(ε + a(a + b + c)*)abc. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.14 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a(a+b)*b. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.15 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a+b)*(aa+bb)(a+b)*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.16 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a*(a + b)b*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.17 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a + b)b*(b + c). Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.18 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão ab(a + b)*ba. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.19 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão xx(x + y + z)*yy. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.20 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a + ε)(b + ba)*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.21 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (b + ε)(b + ba)*(a + ε). Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.22 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a + b)(ab + bc)*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.23 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (c + ε)(a + b)*c. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

onExercício 06.24 Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão a(a + b)*bb(a + b)*a. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.


Recomendamos

Revista Tema Duolingo Java Magazine