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

465 merkkiä lisätty ,  8 vuotta sitten
ei muokkausyhteenvetoa
p (Botti poisti 27 Wikidatan sivulle d:q338047 siirrettyä kielilinkkiä)
Ei muokkausyhteenvetoa
'''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'') 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ä==
 
Yhteydetön kielioppi on nelikko <math>G = (V_t, V_n, P, S)</math>, missä
<math>G = (V\,, \Sigma\,, R\,, S\,)</math>, missä
 
*<math>V_tV</math> on kieliopin päätemerkkien äärellinen joukko
*<math>V_n\Sigma</math> on kieliopin välikkeiden äärellinen joukko
*''PR'' on kieliopin sääntöjen eli produktioiden (äärellinen) joukko
*''S'' on joukon <math>V_nV</math> alkio, kieliopin välikkeisiin kuuluva lähtösymboli
 
*''PR'':n alkiot ovat muotoa
::<math>V_n\Sigma \longrightarrow (V_tV \cup V_n\Sigma)^*</math>, missä * on Kleenen tähti
 
==Esimerkkejä==
:T &rarr; aTbT | bTaT | &epsilon;
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.
 
== Kontekstivapaiden kielten joukon ominaisuuksia ==
Kontekstivapaiden kielten joukko on suljettu yhdisteen, katenaation ja Kleenen tähden suhteen, mutta toisin kuin säännöllisten kielten joukko, se ei ole suljettu leikkauksen tai komplementin suhteen.
 
Mikä tahansa yhden merkin konteksi vapaa kieli on säännöllinen.
 
== Johdot ja jäsennyspuut ==
52

muokkausta