P1 - Teoria da computação - UERJ

Prévia do material em texto

1711 
 
 
Considere a linguagem L1, para as questões 1, 2 e 3, a seguir: 
 
L1 = { w  {0,1}
*
  |w|  2 e w possui pelo menos um par 01 } 
 
Exemplos de cadeias  L1: 01,001,010,011,101,0001,0010,0011,0100,0101,0110,0111, 
1001,1010, 1011, 1101,00001,...,00010, ..., 01000,...,01111, ..., 10001, ..., 11101,... 
 
Exemplos de cadeias  L1: 00,10,11,000,100,110,111,0000,1000,1100,1110,1111, 
...,00000,...,11111,... 
 
1.ª ) Apresente um autômato finito determinístico que reconheça L1. 
 
2.ª ) Apresente uma expressão regular que denote L1. 
 
3.ª ) Apresente uma gramática regular que gere L1. 
 
4.ª) Aplicando o teorema 1 para equivalência entre autômatos finitos e gramáticas 
regulares, que diz “toda linguagem regular é aceita por um AFND”, apresente um 
AFND que reconheça a linguagem gerada pela gramática regular G4 
 
G4 = <{S,A,B,C }, {0,1}, P, S >, onde P é o seguinte conjunto: 
 
S  0A 
S  1B 
A  1C 
A  0S 
B  0C 
B  1S 
C  0B 
C  1A 
C  ε 
 
5.ª) Aplicando o lema 2 para equivalência entre autômatos finitos não determinísticos 
(AFNDs) e autômatos finitos determinísticos (AFDs), que diz “toda linguagem aceita 
por um AFND sem transição- é aceita por um AFD”, construa um AFD equivalente ao 
AFND M5 = <{q0, q1 , q2}{0,1},δ, q0,{ q2}>, cuja função de transição está representada 
pelo diagrama, a seguir: