Atividade Didática I

Prévia do material em texto

UNIVERSIDADE FEDERAL DO AMAZONAS 
INSTITUTO DE COMPUTAÇÃO 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
 
Linguagens Formais e Automata – Atividade Didática I 
Período: 2017/2 Disciplina: IEC087 Linguagens Formais e Automata 
Prof: José Francisco de Magalhães Netto jnetto@icomp.ufam.edu.br 
 
Data: 16/08/2017 
 
Importante: 
• Tarefa individual com consulta a material didático. 
• Sua participação é voluntária; caso não seja do seu interesse participar, sua presença 
será abonada e está liberado de participação. 
• Participando, obedeça as regras do jogo. 
 
Atividade Didática I 
 
Questões 
 
1 Para cada uma das linguagens abaixo dê três strings que pertencem a ela: 
 Linguagem String 
1 
String 
2 
String 
3 
1 {ai cj bi| i, j 
≥ 0} 
 
 
2 {ai bj ck| i + 
k = j} 
 
3 {ai bj | i ≥ 0, 
j ≥ 0 } U a* 
U b* 
 
 
4 {ai bj | 0 ≤ i 
≤ j ≤ 2i} 
 
 
5 {ai+j bi cj| i, j 
> 0} 
 
 
 
 
2. Use as identidades de expressões regulares para estabelecer a seguinte identidade: 
 (a U b)* = (b* (a U λ)b*)* 
 
 * Indique a identidade utilizada em cada passo. 
 
 
UNIVERSIDADE FEDERAL DO AMAZONAS 
INSTITUTO DE COMPUTAÇÃO 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
 
Linguagens Formais e Automata – Atividade Didática I 
Tabela: Identidades de Expressões Regulares 
 
1. Øu = uØ = Ø 
2. λu = λu = u 
3. Ø* = λ 
4. λ* = λ 
5. u U v = v U u 
6. u U Ø = u 
7. u U u = u 
8. u* = (u*)* 
9. u(v U w) = uv U uw 
10. (u U v)w = uw U vw 
11. (uv)*u = u(vu)* 
12. (u U v)* = (u* U v)* 
13. (u U v)* = u*(u U v)*= (u U vu*)* 
14. (u U v)* = (u*v*)* = u*(vu*)* 
15. (u U v)* = (u*v)*u* 
 
Tabela: Identidades de Expressões Regulares 
 
 
 
 
UNIVERSIDADE FEDERAL DO AMAZONAS 
INSTITUTO DE COMPUTAÇÃO 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
 
Linguagens Formais e Automata – Atividade Didática I 
3. Ache a expressão regular que representa o conjunto de strings sobre {a,b,c} que contém as 
substrings aa, bb e cc. 
 
4. Para cada uma das seguintes linguagens, dê um diagrama de estados AFD que aceite as 
linguagens: 
a) (ab)* ba 
b) ((aa)+bb)*