Lista 1 LF afd afn

Prévia do material em texto

1) Para a linguagem a seguir, apresente (i) diagrama de estados de um autômato finito 
determinístico que reconhecem a linguagem, (ii) diagrama de estados de um autômato finito 
não-determinístico reconhece a linguagem e, por fim, (iii) apresente uma expressão regular que 
descreve a linguagem. 
Dessa forma, para a linguagem a seguir, você deverá apresentar dois autômatos e uma 
expressão regular. 
 
Considere Σ = {0,1}. 
 
{w | w possui no máximo uma ocorrência de 00 e exatamente uma ocorrência de 11} 
 
 
 
 
2) Construa autômatos finitos determinísticos que reconheçam para as linguagens sobre o 
alfabeto Σ = {a,b}: 
 
L1 = {w | |w| é divisível por 3} 
L2 = {|w| é ímpar} 
 
onde |w| representa o tamanho da palavra w. 
Construa um autômato finito determinístico que reconhece a união destas linguagens, 
utilizando a técnica vista em aula. 
 
 
 
 
3) Use a construção dada no Teorema 1.39 (Sipser) para converter o autômato finito 
não-determinístico a seguir em um autômato finito determinístico equivalente. 
 
4) O trecho a seguir foi extraído do livro ``[Expressões regulares] uma abordagem divertida'' 
que apresenta expressões regulares dentro do contexto de sua aplicação em linguagens de 
programação: 
 
"Bem resumido, uma expressão regular é um método formal de se especificar um padrão de 
texto. 
 
Mais detalhadamente, é uma composição de símbolos, caracteres com funções especiais, que, 
agrupados entre si, e com caracteres literais, formam uma sequência, uma expressão. Essa 
expressão é interpretada como uma regra que indicará sucesso se uma entrada de dados 
qualquer casar com essa regra, ou seja, obedecer exatamente a todas as suas condições. 
 
Na prática, expressões regulares servem para uma infinidade de tarefas, é difícil fazer uma 
lista, pois elas são úteis sempre que você precisar buscar ou validar um padrão de texto que 
pode ser variável, como: data, horário, número IP, nome de pessoa, endereço de email, 
endereço de Internet, nome de usuário e senha, número de telefone, número de CPF, entre 
outros. " 
 
Baseado na aplicação de expressões regulares em linguagens de programação, apresente 
uma expressão regular para descrever o seguinte padrão para nome de usuário e senha ao 
realizar o login no seu email institucional. 
 
Aqui iremos considerar que o login deve ser um email do tipo: 
nome.sobrenome.aluno@unipampa.edu.br 
 
e que a senha deve necessariamente conter letras, números e caracteres especiais, tendo 
tamanho pelo menos 8. 
 
A sua expressão regular deverá concatenar usuário e senha. Por exemplo: 
 
joao.silva.aluno@unipampa.edu.br 
 
123joao! 
 
Irá ficar: 
 
joao.silva.aluno@unipampa.edu.br​○123joao! 
 
Considere no seu exercício os seguintes alfabetos (para facilitar o seu trabalho): 
 
LMa = {A,B,C, ... , Z} 
LMi = {a,b,c, ... , z} 
Simb = { . , @ , ! , $ , # , % , & , *} 
Num = {0,1,2,3, ... 9} 
mailto:joao.silva.aluno@unipampa.edu.br
5) Apresente um diagrama de estados de um autômato finito determinístico ou 
não-determinístico que reconheça a seguinte linguagem sobre o alfabeto {0,1}: 
 
Predecessor = { w | w representa em binário exatamente o predecessor imediato de uma 
potência de 2} 
 
O predecessor imediato de um número natural n maior do que 0 é o número natural n-1. 
 
Exemplos: 
 
o predecessor de 2 é 1; 
o predecessor de 3 é 2. 
 
OBSERVAÇÃO: é parte do exercício interpretar qual o padrão desses números.