Matematické Fórum

hds · 04. 02. 2014 06:48

Zdravim,
chtel bych poprosit o radu pri sestrojovani automatu nad abecedou {0,1}, ktery prijima slova, jez maji sudy pocet znaku a obshahuji sekvenci 11010. Automat, ktery prijima slova co obsahuji tu sekvenci, se mi povedlo sestavit pomerne bez problemu, ale ani za boha nemuzu prijit na to, jak do nej zahrnout i tu druhou podminku na sudy pocet prvku. Zkousel jsem to delat tak, ze jsem sesmolil nejaky pochybny automat na tu sudost a chtel jej "zkombinovat" s tim automatem na sekvenci, ale z toho mi vysla 18ti stavova motanice (ten na sekvenci mi vychazi na 6 stavu a na sudost na 3 stavy) ve ktere jsem se po chvilce uz ani trocha nevyznal a nechce se mi verit, ze to je spravy postup.(predevsim kvuli nasledne minimalizaci, ktera by byla asi pomerne slozita)
Dekuji za pripadne rady, uz jsem z toho pomerne zoufaly.

hradecek · 05. 02. 2014 17:36

↑ hds:
Na párnosť stačia predsa iba 2 stavy, nie? ... pre prázdne slovo $\varepsilon$ platí: $|\varepsilon|=0$ .
Pre "prienik" dvoch automatov $M_1=(Q_1,\Sigma, \delta_1,q_1,F_1)$ a $M_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ môžeš použiť tzv. synchrónnu paralélnu kompozíciu, kde nový automat bude:
$Q_3&=Q_1\times Q_2=\{{p,q} | p\in Q_1, q\in Q_2\}\\ F_3&=F_1\times F_2=\{{p,q} | p\in F_1, q\in F_2\}\\ q_3&=(q_1,q_2)\\ \delta_3((p,q),a)&=(\delta_1(p,a),\delta_2(q,a))$

Matematické Fórum

#1 04. 02. 2014 06:48

Sestrojeni konecneho automatu

#2 05. 02. 2014 17:36

Re: Sestrojeni konecneho automatu

Zápatí