Surynek 9.6.

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Tyler Durden

Surynek 9.6.

Příspěvek od Tyler Durden »

Jazyk k zařazení: \left\{ucv\:|\:u,v\in\left\{a,b\right\}^*\wedge|u|_a
eq |v|_a\right\}

Věta: Důkaz Myhill-Nerodovy věty (v reakci na to, že u jazyka jsem ukazoval neregularitu přes tuhle větu).

Ten jazyk je bezkontextový - neregularita třeba přes M-N: Nechť máme pravou kongruenci indexu k, uvážím slova a^1c,a^2c,\dots a^{k+1}c\in L. Potom existují dvě slova ve stejné třídě rozkladu podle kongruence. Nechť jsou to a^ic,a^jc, kde i
eq j, potom a^ic.a^i
otin L\wedge a^jc.a^i\in L, spor. Bezkontextovost zásobníkovým automatem, kterej si na zásobník háže áčka a pak je popuje.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“