asked 2014-10-20 09:19:08 +0100
Ahoj, mám zadání, kdy má automat generovat řetězec obsahující bab, ale nesmí se tam vyskytovat abba (z abecedy a a b). Tak jsem si řekl, že si to zkusím udělat přes rozdíl dvou automatů. Nějak jsem ale nenašel postup, jak se takový automat tvoří. Jde to?
Vím že by tenhle příklad šel asi vyřešit i jinak. O to mi teď ale nejde.
answered 2014-10-20 11:01:53 +0100
On jazyk přijímaný automatem je vlastně množina. Množinový rozdíl vypadá nějak takto:
$L_1 \setminus L_2 = L_1 \cap \lnot L_2$
Operace pro průnik a doplněk znáte, pokud tedy uděláš průnik prvního automatu s doplňkem druhého automatu, máš operaci rozdíl automatů. Samozřejmě můžeš vymyslet postup, jak při tvorbě automatu tyto dvě operace udělat najednou, aby to byla skutečně jediná operace, a nemělo by to být složité.
answered 2014-10-20 09:32:06 +0100
U KA lze provádět pouze průnik, sjednocení, zřetězení, doplněk a iteraci. Tohle je příklad na průnik. Uděláš si jeden automat, který příjímá řetězec bab a jeden který nepřijímá abba a průnik je to co chceš
Asked: 2014-10-20 09:19:08 +0100
Seen: 320 times
Last updated: Oct 20 '14
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.
