Prevod konecneho automatu na regularny vyraz

Question

0

Prevod konecneho automatu na regularny vyraz

BI-AAG

asked 2015-12-25 16:15:47 +0100

gandalf
113 ●27 ●30 ●37

Zdravim, pripravujem sa na druhy test z AAG, a riesim nejake priklady z minulych rokov. Mam tu jeden prevod, ktory je dost blby a neviem, ci postupujem spravne, preto ak by sa nasiel niekto, kto by to skontroloval, bol by som rad.

1 = t2 + eps
2 = s2 + s5 + t4
3 = s2 + t4 + t5 + eps
4 = s3 + t1
5 = s1 + t4

2 =  s* ( s5 + t4)
3 (dosaduzjem do s2 a t4 ) = ts*(ss*s5 + ss*st4 + tt1 + t5 + eps)
4 (dosadzujem za s3) = sts*ss*s5 + sts*ss*st4 + sts*tt1 + sts*t5 + sts* + t4  = 
   (dosadim za s5) sts*ss*ss1 + sts*ss*ss4 + sts*ss*st4 + sts*tt1 + sts*ts1 + sts*ts4 + ts* = 
    (sts*ss*ss + sts*ss*ss + sts*ts)*(sts*ss*ss1+ sts*tt1 + sts*ts1 + ts*)
 1 (dosadim za t2) = ts*s5 + ts*t4 + eps = 
   (dosadim za s5) = ts*ss1 + ts*st4 + ts*t4 + eps
  .....

Dalej by som za 4 dosadil tam mam uz len same 1cky a to uz by som vedel upravit, kazdopadne vyraz na "100" riadkov. Je tento priklad fakt taky zlozity, a neda sa riesit jednoduchsie? Dakujem.

edit retag flag offensive close delete

Answer 1

0

answered 2015-12-26 21:00:59 +0100

Ondřej Máca
192 ●7 ●11 ●20

updated 2016-01-10 13:33:36 +0100

Ta gramatika moc hezky nevypadá. Ve trojce ti myslím utekla závorka, ale jinak mi to taky vychází dost složitě. Nevím, ale který stav automatu byl počáteční, proto jsem to ani nezkoušel dokončit. Ono by stejně bylo lepší, kdybych viděl celý automat. Možná by to k něčemu pomohlo..

3 = (ts)*(ss*s5 + ss*t4 + tt1 +t5 + eps)
4 = s(ts)*(ss*s5 + ss*t4 + tt1 +t5 + eps) + t1
4 = s(ts)*ss*s5 + s(ts)*ss*t4 + s(ts)*tt1 + s(ts)*t5 + s(ts)* + t1
4 = (s(ts)*ss*t)*(s(ts)*ss*s5 + s(ts)*tt1 + s(ts)*t5 + s(ts)* + t1)

EDIT: Tak nakonec se ukazuje jako nejlepší dosazovat na začátku co nejvíce to jde, tím se zbavíš několika terminálů a potom už to celkem jde. Ukážu začátek mého postupu, celé se mi to sem psát nechce:

Dosadím za 5
1 = t2 + eps
2 = s2 + s(s1 + t4) + t4 = s2 + ss1 + st4 + t4 = ss1 + (st + t)4
3 = s2 + t4 + t(s1 + t4) + eps = s2 + t4 +ts1 + tt4 + eps = s2 + (t +tt)4 +ts1 + eps
4 = s3 + t1

Přepíši pro přehlednost 
1 = t2 + eps
2 = ss1 + (st + t)4
3 = s2 + (t +tt)4 +ts1 + eps
4 = s3 + t1

Dosadím za 4
1 = t2 + eps
2 = ss1 + (st + t)(s3 + t1)
3 = s2 + (t +tt)(s3 + t1) +ts1 + eps

edit flag offensive delete publish link

Comments

https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-aag/aag_test_2014-12-10_1830_zelena tu je povodny. Diky za odpoved.

gandalf ( 2015-12-30 13:27:38 +0100 )edit

Prevod konecneho automatu na regularny vyraz

1 Answer

Comments

Your answer

Question tools

Stats

Related questions