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

p
Poistin typerän äärettömän rekursio mahdollisuuden
p (Poistin typerän äärettömän rekursio mahdollisuuden)
'''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ä==
<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
35

muokkausta