Yhteydetön kielioppi

Yhteydetön kielioppi tai kontekstiton kielioppi on kielitieteessä ja tietojenkäsittelytieteessä formaali kielioppi, jossa jokainen kirjoitussääntö on muotoa

V → w

missä V on välike ja w päätemerkeistä ja/tai välikkeistä koostuva merkkijono. Korvauksen voi tehdä aina riippumatta V:n kontekstista eli sitä ympäröivistä symboleista; tästä nimi yhteydetön tai kontekstiton. Formaali kieli on yhteydetön jos sen tuottaa yhteydetön kielioppi.

Formaali määritelmä

Yhteydetön kielioppi on nelikko $G=(V_{t},V_{n},P,S)$, missä

• $V_{t}$ on kieliopin päätemerkkien äärellinen joukko
• $V_{n}$ on kieliopin välikkeiden äärellinen joukko
• P on kieliopin sääntöjen eli produktioiden (äärellinen) joukko
• S on joukon $V_{n}$ alkio, kieliopin välikkeisiin kuuluva lähtösymboli

• P:n alkiot ovat muotoa

$V_{n}\longrightarrow (V_{t}\cup V_{n})^{*}$

Esimerkkejä

Esimerkki 1:

Yksinkertainen yhteydetön kielioppi on

S → aSb | ε

Kielioppi tuottaa kielen $\{a^{n}b^{n}:n\geq 0\}$

Esimerkki 2:

Seuraava kielioppi tuottaa sellaisista aakkoston {a,b} merkkijonoista koostuvan kielen, joissa on eri määrä merkkejä a ja b.

S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

Tässä T voi tuottaa kaikki merkkijonot, joissa on sama määrä a:ta ja b:tä. U tuottaa merkkijonot, joissa on enemmän a- kuin b-merkkejä ja V vastaavasti sellaiset jonot, joissa a:ta on vähemmän.