"mitteterminale" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt


 2) mitteterminaalid nimetatakse ümber A1-ks, A2-ks jne. 3) produktsioonid asendatakse kujule aA1A2A3… Regulaarsete keelte hulk on KV keelte pärisosahulk. Vaatame kasvõi pumpamise lemmasid: uvjw on lihtsalt uvjwxjy erijuht ehk uvjwjxjy= u(vwx)jy. 13 Taandatud KV grammatikad. Iga KV keele jaoks leidub teda genereeriv taandatud KV grammatika: 1) ε-vaba (puuduvad tühja parema poolega produktsioonid, v.a S → ε, kui ε kuulub sellesse keelde) 2) ei sisalda kasutuid sümboleid ehk mitteterminale, millest ei saa tuletada terminaalseid sõnesid; 3) ei sisalda saavutamatuid sümboleid (mis nkn ei teki ühegi produktsiooni käigus kunagi); 4) tsüklivaba ehk ühegi mitteterminaali ei saa temast endast tuletada. 1. ja 4. tingimuse täitmiseks piisav, kui eemaldada ε-d ja ahelproduktsioonid. Eemaldada tuleb ka sümbolid, milleni nkn kunagi ei jõuta. Ja tuleb vaadata, et S * wXy * wxy (lõpuks aint terminaalid). 14 KV-keelte tarvilikkuse tingimus.