asked Oct 20 '14
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 Oct 20 '14
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š
answered Oct 20 '14
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é.
Asked: Oct 20 '14
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.
