Lista de Exercícios de Expressões Regulares

Ministério da Educação Universidade Tecnológica Federal do Paraná[pic 1]

Câmpus Medianeira

Disciplina: Linguagens Formais e Autômatos

Trabalho – Expressões Regulares

---

[pic 2]

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ[pic 3]

[pic 4][pic 5]

1. Construa as expressões regulares que denotem as seguintes linguagens, considerando o alfabeto Σ = {a, b}

1. { w pertence a Σ* | |w| >= 3 }
2. { w pertence a Σ* | |w| é ímpar }

1. { w pertence a Σ* | w contenha um número ímpar de símbolos “a” }
2. { w pertence a Σ* | w começa com o símbolo “a” e tem tamanho par }
3. { w pertence a Σ* | w contenha no mínimo dois símbolos “a” ou exatamente dois símbolos “b” }
4. { w pertence a Σ* | w termina com símbolo repetido }
5. { w pertence a Σ* | w não termina com símbolo repetido }
6. { w pertence a Σ* | w contenha exatamente uma repetição de símbolos }.

---

1. Trabalho – Autômatos Finitos Não-Determinísticos - AFN Considerando o alfabeto Σ = {a, b, c}, construa AFNs que aceitam as seguintes linguagens: 1 - {w є Σ* | w contenha a subcadeia “abab”}. Exemplos: abbababc - aceita caaaaaba – rejeita 2 - {w є Σ* | w pode conter uma ou ambas as subcadeias “ab” e “abc”}. Exemplos: aabaabc - aceita bacacba – rejeita 3 - {w є Σ* | w contenha pelo menos dois símbolos “a” ou, exatamente dois símbolos “b”}. 4 - {w є Σ* | o último símbolo de w ocorra pelo menos mais uma vez anteriormente em w e os símbolos que aparecerem nesta subcadeia sejam alfabeticamente menores que o referido símbolo}. Exemplos: cacbaabc – aceita cccbaaab - aceita bbcacba – rejeita, porque na subcadeia delimitada pelo par de símbolos “a” aparecem símbolos alfabeticamente maiores (“c” e “b”) 5 - {w є Σ* | o último símbolo de w seja diferente do primeiro }. 6 - {w є Σ* | o último símbolo de w tenha ocorrido antes }. 7 - {w є Σ* | w contenha duas ocorrências da subcadeia “abc” com um número ímpar de símbolos entre elas}. 8 - { w є Σ* | w não termina com símbolo repetido } 9 - { w є Σ* | w contenha exatamente uma repetição de símbolos }. 10 - Um navio tenta transmitir dados para uma base localizada no continente em intervalos randômicos. A base deve continuamente ouvir e reconhecer quando uma transmissão inicia e assim gravar os dados que seguem. O protocolo de comunicação determina que o início da transmissão seja sinalizado pela cadeia 010010 e o término é sinalizado pela cadeia 000111. Elabore uma AFN para representar este comportamento. Ministério da Educação Universidade Tecnológica Federal do Paraná Câmpus Medianeira Disciplina: Linguagens Formais e Autômatos UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ PR

...