حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۳

با توجه با گرامر مستقل از متن زیر به سوالات پاسخ دهید:

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 ها را تولید می کند.