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

تمرین

نشان دهید که کلاس زبان‌های مستقل از متن تحت عمل‌های اجتماع، اتصال و بستار بسته‌است.

حل

الف) کلاس زبان‌های مستقل از متن تحت عمل اجتماع (union) بسته‌است:

اگر L1 و L2 زبان‌های مستقل از متن باشند،

در اینصورت گرامرهای مستقل از متنی مانند G1=(V1,Z1,R1,S1)و G2=() وجود دارند چنان که L1=L(G1) و L2=L(G2).

اگر لازم باشد نمادهای غیر پایانه ی g1 و g2 را چنان تغییر نام می‌دهیم که دو مجموعه از هم جدا باشند(اشتراکشان صفر شود)

و بنابراین هیچ کدام شامل نماد S نخواهد بود. حال گرامر جدید G را چنان می‌سازیم که l(g) = ل)ل2. g تمامی قوانین g1 و g2 را شامل خواهد بود. حال به G نماد آغازین جدیدِ S و قوانین s->s1 و s->s2 رااضافه می‌کنیم. این دو قانون جدید به G اجازه می‌دهند که رشته‌ای را تولید کند اگر و فقط اگر حداقل یکی از گرامرهای g1 و g2 آن را تولید نمایند. در این صورت داریم: ل=

ب) کلاس زبان‌های مستقل از متن تحت عمل اتصال بسته‌است:

اگر l1 و l2 زبان‌های مستقل از متن باشند، در اینصورت گرامرهای مستقل از متن G1 و g2 وجود خواهند داشت به قسمی که l1=l(g1) و l2=l(g2). در صورت نیاز، نمادهای ناپایانه ی G1 و G2 را تغییر نام دهید به طوری که دو مجموعه جدا از هم باشند و هیچ کدام شامل نماد S نباشند. حال گرامر جدید G را طوری می‌سازیم که l(g1) = . G همه ی قوانین هر دوی g1 و G2 را در بر خواهد داشت. حال به G نماد آغاز جدید S و قانون جدید S->S1S2 را اضافه خواهیم کرد. در نتیجه خواهیم داشت :

ج) کلاس زبان‌های مستقل از متن تحت عمل بستار بسته‌است:

اگر زبان مستقل از متنی باشد، در این صورت گرامر مستقل از متن G وجود خواهد داشت به قسمی کهl1=l(g1) است. در صورت نیاز نمادهای ناپایانی g1 را تغییرنام دهید به قسمی که V1 دیگر نماد S را شامل نشود. حال گرامر جدید g را چنان می‌سازیم که L(G)= L(G1)*. G تمامی قوانین G1 را در برخواهد داشت. حال به G نماد آغاز جدید S، به همراه دو قانون جدید S->e و S->ss1 را اضافه می‌کنیم. حال G