Matematické Fórum

Zdravím,

při přípravě na zápočtovou písemku jsem narazil na automat, se kterým si nevím rady. Sudost/lichost už jsem v deterministických KA řešil několikrát, překvapivě mi to ale komplikuje požadavek na obsahování 0 a 1 alespoň jedenkrát v řetězci. Ten navíc musí být sudý, aby jej automat přijal.

Cílem je přijímat řetězce typu 001111, 110000, 101010, 111110, 011111, ... apod. Abeceda E = {0,1}, ale to už se opakuji. V prvním stavu je asi nezbytné provést rozdělení pro nulu a jedničku do samostatných stavů a v nich dále ošetřit druhý znak + sudost, všechna řešení mi ale fungují pouze částečně (nic 100% dobře). Snažil jsem se pátrat mezi spolužáky a údajně je k řešení potřeba 8 stavů, povolené maximum je pak 10.

Za případnou radu předem mnohokrát děkuji a pokud se někdy setkáme, nezůstanu nic dlužen :-).