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

613 merkkiä lisätty ,  16 vuotta sitten
ei muokkausyhteenvetoa
*''P'':n alkiot ovat muotoa
::<math>V_n \longrightarrow (V_t \cup V_n)^*</math>
 
==Esimerkkejä==
 
'''Esimerkki 1:'''
 
Yksinkertainen yhteydetön kielioppi on
:S &rarr; aSb | &epsilon;
Kielioppi tuottaa kielen
<math> \{ a^n b^n : n \ge 0 \} </math>
 
'''Esimerkki 2:'''
 
Seuraava kielioppi tuottaa sellaisista aakkoston {a,b} merkkijonoista koostuvan kielen, joissa on eri määrä merkkejä a ja b.
:S &rarr; U | V
:U &rarr; TaU | TaT
:V &rarr; TbV | TbT
: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.
 
{{Formaalit kielet}}
19 616

muokkausta