Baixe o app para aproveitar ainda mais
Prévia do material em texto
Exercícios – Lista 2 1. Desenvolva AFD que reconheçam as seguintes linguagens sobre o alfabeto ∑ = {a,b} a) {w | o sufixo de w é aa} b) {w | w possui aaa como subpalavra} c) {w | w possui número ímpar de a e número ímpar de b} d) {w | w possui número par de a e ímpar de b ou w possui número par de b e ímpar de a} e) {w | o quinto símbolo da direita para a esquerda de w é a} Dica: o autômato resultante possui um número relativamente grande de estados. 2. Desenvolva autômatos finitos não determinísticos que reconheçam as seguintes linguagens sobre o alfabeto ∑ = {a, b}. a) Qualquer ocorrência de a é imediatamente sucedida por b. b) Qualquer ocorrência de a é imediatamente antecedida e imediatamente sucedida por b. 3. Quais das seguintes palavras são aceitas pelos autômatos finitos não determinísticos sobre o alfabeto ∑ = {a,b}. a) e, aa, bb, aba, bbaaba, abababababa. b) e, bb, bab, bbbaaa, bbbbbbababababa 3. Desenvolva autômatos finitos não determinísticos, com ou sem movimentos vazios, que reconheçam as seguintes linguagens sobre o alfabeto ∑ = {a,b} a) {w1w2w1 | w2 é qualquer e |w1| = 3 } b) {w | o decimo símbolo da direita para a esquerda de w é a} c) {w | w possui número de símbolos a e b e (qualquer prefixo de w possui, no máximo, dois a a mais que b ou qualquer prefixo de w possui, no máximo, dois b a mais que a) } 4. Desenvolva, sobre o alfabeto ∑ = {a,b,c}: a) Autômato finito não determinístico que reconheça a seguinte linguagem: {w | a ou bb ou ccc é sufixo de w} b) Autômato finito não determinístico com movimentos vazios que reconheça a seguinte linguagem: {w | aa ou bb é subpalavra e cccc é sufixo de w}
Compartilhar