Ask Your Question
0

Prevod konecneho automatu na regularny vyraz

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

gandalf gravatar image

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

1 Answer

Sort by » oldest newest most voted
0

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

Ondřej Máca gravatar image

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 more

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

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

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

Seen: 200 times

Last updated: Jan 10