Normalmente os DFAs sao utilizados para a geracao de codigo
fonte, dado queeles representam uma funcao total (existem
transicoes em todos os estados paratodos os smbolos do alfabeto).
Este trabalho visa exercitar o uso de umalinguagem de programacao
para a representacao de DFAs e a geracao de codigofonte
equivalente.
Escreva um programa que receba um DFA como entrada e gere um
outroprograma que reconheca cadeias segundo este DFA.
Entrada: Um DFA (e livre a escolha do modo de
representacao).Sada: Um programa na linguagem de programacao de sua
escolha que si-
mule o DFA de entrada.
Observacao 1: Nao podem ser utilizados pacotes de manipulacao de
automatospara este trabalho.
2 Exemplo
Considere o seguinte DFA de exemplo, mostrado na Figura 2.
1
Este DFA pode ser representado (e e, pelo JFLAP) da seguinte
forma:
1 2 < ! Created wi th JFLAP 6 . 4 . >3 4 f a5 6 7 64 .08
57 .09 < l a b e l>010 < i n i t i a l />11 12 13 268
.014 57 .015 < l a b e l>1 ,3 ,216 < f i n a l />17 18
19 58 .020 183 .021 < l a b e l>2 ,322 < f i n a l />23
24 25 247 .026 273 .027 < l a b e l>328 < f i n a l
/>29 30 31 432 .032 187 .033 < l a b e l>Trap State34 35
36 137 438 b39 40 41 442 443 b44 45 46 247 448 b
Apos analisar os dados de entrada, um possvel codigo fonte
gerado peloprograma criado neste trabalho seria:
1 #include 2 #include 3 #include 4 #include 56 us ing namespace
std ;78 int main ( int argc , char argv [ ] ) {
3
9 char s t r [ 2 0 ] ; char atua l ;10 s can f ( %s , &s t r
) ;11 int ult imo = s t r l e n ( s t r ) ;12 int i = 1;13 q0 :14
atua l = s t r [++ i ] ;15 i f ( i == ult imo )16 goto r e j e i t
a ;17 else i f ( a tua l == a )18 goto q1 ;19 else i f ( a tua l ==
b )20 goto q2 ;21 q1 :22 atua l = s t r [++ i ] ;23 i f ( i == ult
imo )24 goto a c e i t a ;25 else i f ( a tua l == a )26 goto q1
;27 else i f ( a tua l == b )28 goto q4 ;29 q2 :30 atua l = s t r
[++ i ] ;31 i f ( i == ult imo )32 goto a c e i t a ;33 else i f (
a tua l == a )34 goto q3 ;35 else i f ( a tua l == b )36 goto q4
;37 q3 :38 atua l = s t r [++ i ] ;39 i f ( i == ult imo )40 goto a
c e i t a ;41 else i f ( a tua l == a )42 goto q4 ;43 else i f ( a
tua l == b )44 goto q4 ;45 q4 :46 atua l = s t r [++ i ] ;47 i f (
i == ult imo )48 goto r e j e i t a ;49 else i f ( a tua l == a )50
goto q4 ;51 else i f ( a tua l == b )52 goto q4 ;53 r e j e i t a
:54 p r i n t f ( Re j e i t a \n ) ;55 goto f im ;56 a c e i t a
:57 p r i n t f ( Aceita \n ) ;58 fim :
4
59 p r i n t f ( %c\n , s t r [ i ] ) ;60 system ( PAUSE ) ;61
return EXIT SUCCESS ;62 }
