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

4 merkkiä poistettu ,  14 vuotta sitten
p
ei muokkausyhteenvetoa
(ainakin tampereella ja helsingissä ne ovat välisymboleita)
p
'''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ä==
==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]]).
19 616

muokkausta