Lista de Exercícios - Autômatos e Expressões

Prévia do material em texto

Universidade	
  Federal	
  Rural	
  	
  de	
  	
  Pernambuco	
  
Departamento	
  de	
  Estatística	
  e	
  Informática	
  
Licenciatura	
  em	
  Computação	
  
Teoria	
  da	
  Computação	
  
Prof.	
  	
  George	
  	
  Gomes	
  	
  Cabral	
  
	
  
	
  
1a	
  lista	
  de	
  exercícios	
  	
  1. Forneça	
  a	
  descrição	
  formal	
  das	
  máquinas	
  M1	
  e	
  M2	
  abaixo:	
  
	
   	
  	
  	
  	
  	
  	
  	
  M1	
  	
  	
   	
   	
   	
   	
  	
  	
  	
  	
  M2	
  	
  2. Sendo	
  ∑	
  =	
  {a,	
  b},	
  construa	
  os	
  diagramas	
  de	
  estados	
  dos	
  AFDs	
  para	
  as	
  seguintes	
  linguagens:	
  a. {w	
  |	
  w	
  tem	
  um	
  numero	
  par	
  de	
  as	
  e	
  um	
  ou	
  dois	
  bs}	
  b. {w	
  |	
  w	
  tem	
  comprimento	
  par	
  e	
  um	
  numero	
  impar	
  de	
  as}	
  c. {w	
  |	
  w	
  tem	
  um	
  numero	
  par	
  de	
  as	
  e	
  cada	
  a	
  é	
  seguido	
  por	
  um	
  b}	
  d. {w	
  |	
  w	
  não	
  contem	
  a	
  cadeia	
  aab}	
  e. {w	
  |	
  w	
  é	
  qualquer	
  cadeia	
  que	
  não	
  está	
  em	
  a*b*}	
  	
  3. Sendo	
  ∑	
  =	
  {a,	
  b},	
  construa	
  os	
  diagramas	
  de	
  estados	
  dos	
  AFNs	
  para	
  as	
  seguintes	
  linguagens:	
  a. {w	
  |	
  w	
  pertence	
  à	
  linguagem	
  a*b*a+}	
  (com	
  três	
  estados)	
  b. {w	
  |	
  w	
  contem	
  a	
  cadeia	
  abab}	
  (com	
  5	
  estados)	
  c. {w	
  |	
  w	
  é	
  a	
  linguagem	
  a*(bba+)*}	
  	
  	
   4. Converta	
  o	
  AFN	
  da	
  figura	
  abaixo	
  em	
  um	
  AFD	
  e	
  depois	
  apresente	
  apenas	
  os	
  estados	
  alcançáveis	
  a	
  partir	
  do	
  estado	
  inicial.	
  
	
  	
  5. 	
   a. Forneça	
  um	
  AFN	
  que	
  reconheça	
  a	
  linguagem	
  (01	
  U	
  001	
  U	
  010)*.	
  b. Converta	
  esse	
  AFN	
  em	
  um	
  AFD	
  equivalente.	
  Apresente	
  apenas	
  a	
  parte	
  do	
  AFD	
  que	
  é	
  alcançável	
  a	
  partir	
  do	
  estado	
  inicial.