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

478 merkkiä lisätty ,  16 vuotta sitten
ei muokkausyhteenvetoa
(alkua)
 
:V → ''w''
missä V on välike ja ''w'' päätemerkeistä 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ä==
 
Yhteydetön kielioppi on nelikko <math>G = (V_t, V_n, P, S)</math>, missä
 
*<math>V_t</math> on kieliopin päätemerkkien äärellinen joukko
*<math>V_n</math> on kieliopin välikkeiden äärellinen joukko
*''P'' on kieliopin sääntöjen eli produktioiden (äärellinen) joukko
*''S'' on joukon <math>V_n</math> alkio, kieliopin välikkeisiin kuuluva lähtösymboli
 
*''P'':n alkiot ovat muotoa
::<math>V_n \longrightarrow (V_t \cup V_n)^*</math>
 
{{Formaalit kielet}}
19 616

muokkausta