Surynek 9.6.

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.