Wikipedia

Ero sivun ”Yhteydetön kielioppi” versioiden välillä

Selaa historiaa interaktiivisesti
[arvioimaton versio][arvioimaton versio]
← Vanhempi muutosUudempi muutos →
Poistettu sisältö Lisätty sisältö
VisuaalinenWikiteksti
ainakin tampereella ja helsingissä ne ovat välisymboleita
pEi muokkausyhteenvetoa
Rivi 1:
'''Yhteydetön kielioppi''' tai '''kontekstiton kielioppi''' on [[kielitiede|kielitieteessä]] ja [[tietojenkäsittelytiede|tietojenkäsittelytieteessä]] [[formaali kielioppi]], jossa jokainen kirjoitussääntö on muotoa
:V → ''w''
missä V on ''välike'' tai (''välisymboli'') ja ''w'' ''päätemerkeistä'' tai (''päätesymboleista'') 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 kieli|yhteydetön]] jos sen tuottaa yhteydetön kielioppi.
 
==Formaali määritelmä==
Rivi 58:
==Normaalimuodot==
 
Kukin yhteydetön kielioppi voidaan muuttaa vastaavaksi [[Chomskyn normaalimuoto|Chomskyn normaalimuodossa]] tai [[Greibachin normaalimuoto|Greibachin normaalimuodossa]] olevaksi kieliopiksi,; jälkimmäinen sillä ehdolla, ettei kielioppi tuota tyhjää merkkijonoa. "Vastaava" tarkoittaa tässä sitä, että kieliopit tuottavat saman kielen.
 
Chomskyn normaalimuodossa olevan kieliopin produktiot ovat erityisen yksinkertaisia, minkä vuoksi tällä normaalimuodolla on sekä teoreettisia että käytännön sovelluksia. Sen avulla voidaan esimerkiksi konstruoida algoritmi, joka ratkaisee kuuluuko annettu merkkijono kieliopin tuottamaan kieleen vai ei ([[CYK-algoritmi]]).
Noudettu kohteesta ”https://fi.wikipedia.org/wiki/Yhteydetön_kielioppi”