Sztochasztikus automaták

Az előadás célja a sztochasztikus automaták elmélete alapjainak bemutatása.

Azonosító: PV1-SZA

Ajánlott a következő hallgatóknak:  A programtervező matematikus szak I1 sávján tanulóknak választható tantárgyként, alkalmazott matematikus hallgatóknak, programtervező informatikus halltatóknak.

Óraszám: 2+0

Számonkérés módja: kollokvium 

Előfeltétel:

     Az I1 sávon a PV1-ANY2 Automaták és nyelvek 2 tárgy, más hallgatóknak legalább egy bevezető számításelmélet, illetve valószínűségelmélet tantárgy.

Javasolt félév: A tanulmányok 6-10 féléve.

Tematika:

• Alfabetikus leképezések (hossztartó, kezdőszelet-tartó), maradékleképezések.
• A Mealy-automata, az általa megvalósított alfabetikus leképezés, példa. Kritérium arra, hogy egy alfabetikus leképezés megvalósítható legyen Mealy-automatában.
• Moore-automata és ekvivalencája a Mealy-automatákkal.
• Nyelvek definiálása Mealy- és Moore-automatákban és kapcsolatuk a reguláris nyelvekkel.
• A sztochasztikus automaták definíciója, az általuk megvalósított sztochasztikus leképezés, példák.
• Az állapotszám minimalizálása sztochasztikus automatákban (redukált, minimális és erősen redukált automata, példák).
• Sztochasztikus nyelvek, sztochasztikus nyelvek felismerése sztochasztikus automatákban végbetűvel.
• Speciális sztochasztikus automaták (Mealy, Moore, megjelölt állapotú). Sztochasztikus nyelvek felismerése megjelölt állapotú sztochasztikus automatákban.
• Sztochasztikus automatákban reprezentálható „közönséges” nyelvek, az m-adikus automata.

Irodalom:

• Azaria Paz, Introduction to Probabilistic Automata, Academic Press, New York and London, 1971.
• V. Claus, Stochastische Automaten, B.G.Teubner Stuttgart, 1971.