Ero sivun ”Yhteydetön kielioppi” versioiden välillä
| [katsottu versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
p Poistin typerän äärettömän rekursio mahdollisuuden |
||
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'' (''välisymboli'',) joka ei saa olla tyhjä, ja ''w'' ''päätemerkeistä'' (''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. Kielioppi on kontekstiton jos ja vain jos se voidaan tunnistaa [[pinoautomaatti|pinoautomaatilla]].
==Formaali määritelmä==
Rivi 8:
<math>G = (V\,, \Sigma\,, R\,, S\,)</math>, missä
*<math>V</math> on kieliopin päätemerkkien äärellinen joukko, joka ei sisällä nollaa eli tyhjää merkkiä
*<math>\Sigma</math> on kieliopin välikkeiden äärellinen joukko
*''R'' kieliopin sääntöjen eli produktioiden (äärellinen) joukko
| |||