حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۳
ظاهر
با توجه با گرامر مستقل از متن زیر به سوالات پاسخ دهید:
R->XRX|S S->aTb|bTa T->XTX|x|ε X->a|b
الف)نمادهای پایانه:a,b - نمادهای ناپایانه: A,B,X,T,R – نماد شروع :R
ب)سه رشته که در (L(G هستند: ab,aabb,aaabbb
پ)سه رشته که در گرامر نیستند: b,bb,aaaa
ت)T=>a b a درست است چون T=>XTX=>aTX=>aXX=>aba
ث)T=>*aba درست
ج)T=>T نادرست
چ)T=>*T درست
ح)XXX=>*aba درست
خ)X=>*aba نادرست
د)T=>*XX درست
ذ)T=>*XXX درست
ر)T=>* ε درست
ز)این زبان دنباله ای از a و b ها را تولید می کند.