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 yhteydettömästä kielestä on ${\displaystyle 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 ${\displaystyle S\to aSb~|~ab}$, ja sen hyväksyy pinoautomaatti ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta ,q_{0},\{q_{f}\})}$ jossa ${\displaystyle \delta }$ on määritelty seuraavasti::

${\displaystyle \delta (q_{0},a,z)=(q_{0},a)}$

${\displaystyle \delta (q_{0},b,ax)=(q_{1},x)}$

${\displaystyle \delta (q_{1},b,ax)=(q_{1},x)}$

${\displaystyle \delta (q_{1},b,bz)=(q_{f},z)}$

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