Yhteydetön kieli

Yhteydetön eli kontekstiton kieli on formaali kieli, jonka tunnistaa jokin pinoautomaatti. Yhteydettömän kielen tuottaa jokin yhteydetön kielioppi.

Yhteydettömillä kielillä on paljon sovelluksia ohjelmointikielissäMalline:Lähde; esimerkiksi useimmat aritmeettiset lausekkeet voidaan tuottaa yhteydettömillä kieliopeilla.

Esimerkki

Esimerkki yhteydettömästä kielestä on $L=\{a^n{b}^n:n\ge 1\}$ eli kieli, joka sisältää kaikki sellaiset merkkijonot, joissa on ensin tietty määrä merkkejä a ja sen jälkeen saman verran merkkejä b. L:n tuottaa kielioppi $S\to aSb|ab$, ja sen hyväksyy pinoautomaatti $M=(\{q_0,q_1,q_f\},\{a\},\{a,b,z\},\delta ,q_0,\{q_f\})$ jossa $\delta$ on määritelty seuraavasti::

$\delta (q_0,a,z)=(q_0,a)$

$\delta (q_0,b,ax)=(q_1,x)$

$\delta (q_1,b,ax)=(q_1,x)$

$\delta (q_1,b,bz)=(q_f,z)$

Lähteet

• Malline:Kirjaviite