Ero sivun ”Yhteydetön kielioppi” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Ei muokkausyhteenvetoa |
Ei muokkausyhteenvetoa |
||
Rivi 32: | Rivi 32: | ||
:T → aTbT | bTaT | ε |
: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. |
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. |
||
== Johdot ja jäsennyspuut == |
|||
On kaksi tapaa kuvata kuinka tietty merkkijono voidaan tuottaa annetusta kieliopista. Yksinkertaisempi tapa on listata peräkkäiset symbolijonot alkaen lähtösymbolista ja päättyen lopulliseen merkkijonoon. Jos jokaisessa johdon askeleessa produktiota käytetään merkkijonon vasemmanpuoleisimpaan välikkeeseen, kyseessä on ns. ''vasen johto'', vastaavasti voidaan määritellä ''oikea johto''. Esimerkiksi seuraavassa kieliopissa |
|||
:S → S + S | 1 |
|||
merkkijonon "1 + 1 + 1" voi tuottaa vasemmalla johdolla (S → S + S → 1 + S → 1 + S + S → 1 + 1 + S → 1 + 1 + 1) tai oikealla johdolla (S → S + S → S + 1 → S + S + 1 → S + 1 + 1 → 1 + 1 + 1). |
|||
{{Formaalit kielet}} |
{{Formaalit kielet}} |
Versio 20. lokakuuta 2005 kello 19.52
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 , missä
- on kieliopin päätemerkkien äärellinen joukko
- on kieliopin välikkeiden äärellinen joukko
- P on kieliopin sääntöjen eli produktioiden (äärellinen) joukko
- S on joukon alkio, kieliopin välikkeisiin kuuluva lähtösymboli
- P:n alkiot ovat muotoa
Esimerkkejä
Esimerkki 1:
Yksinkertainen yhteydetön kielioppi on
- S → aSb | ε
Kielioppi tuottaa kielen
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.
Johdot ja jäsennyspuut
On kaksi tapaa kuvata kuinka tietty merkkijono voidaan tuottaa annetusta kieliopista. Yksinkertaisempi tapa on listata peräkkäiset symbolijonot alkaen lähtösymbolista ja päättyen lopulliseen merkkijonoon. Jos jokaisessa johdon askeleessa produktiota käytetään merkkijonon vasemmanpuoleisimpaan välikkeeseen, kyseessä on ns. vasen johto, vastaavasti voidaan määritellä oikea johto. Esimerkiksi seuraavassa kieliopissa
- S → S + S | 1
merkkijonon "1 + 1 + 1" voi tuottaa vasemmalla johdolla (S → S + S → 1 + S → 1 + S + S → 1 + 1 + S → 1 + 1 + 1) tai oikealla johdolla (S → S + S → S + 1 → S + S + 1 → S + 1 + 1 → 1 + 1 + 1).
Automaattiteoria: formaalit kielet ja formaalit kieliopit | |||
---|---|---|---|
Chomskyn hierarkia |
Kielioppi | Kieli | Tunnistusautomaatti |
luokka 0 | Rajoittamaton | Rekursiivisesti numeroituva | Turingin kone |
Rajoittamaton | Rekursiivinen | Totaalinen Turingin kone | |
luokka 1 | Yhteysherkkä | Yhteysherkkä | Lineaarisesti rajoitettu |
luokka 2 | Yhteydetön | Yhteydetön | Pinoautomaatti |
luokka 3 | Säännöllinen | Säännöllinen | Äärellinen |
Kukin luokka on sen yläpuolisen luokan aito osajoukko. |