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ä^lähde?; esimerkiksi useimmat aritmeettiset lausekkeet voidaan tuottaa yhteydettömillä kieliopeilla.

Esimerkki

Esimerkki yhteydettömästä kielestä on $L=\{a^{n}b^{n}:n\geq 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

• Ruzzo, Walter Lawrence: General context-free language recognition. Väitöskirja : University of California. Ann Arbor (Mich.): UMI, 1978. (englanniksi)