Theory of Computing > QUESTIONS & ANSWERS > CS 421 Theory of computing HW3D (based on for Week 12b-13b topics) Proofs with CFL California State (All)

CS 421 Theory of computing HW3D (based on for Week 12b-13b topics) Proofs with CFL California State University, San Marcos

Document Content and Description Below

California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii – HW3D (based on for Week 12b-13b topics) Proofs with CFL ===============================================... ================= DUE: Week 13 Friday before midnight TOTAL: 20 pts ** Name: **Qian Zhu Your answers in black. ===================================================================--------------------------------- ------------------------------------------------------------------------------------ Questions from Week12b Notes [2pts per prompt = 16 pts] ------------------------------------------------------------------------------------ Try Pumping Lemma contradiction to prove that L is not CFL: Given any N Selected long Give the 4 columns for each possible vwx location. where is vwx repeat factor I result__________result is in L?___________ Thus, there was no way to break S into uvwxy and repeat or skip v and x as much as we want. We found a counter example S. Conclusion: QED Q1. If you had gotten stuck with the above proof (i.e. the PL holds), what could you have concluded? --------------------------------------------------------------- Questions from Week13a notes [4 pts] -------------------------------------------------------------- ##Inter7* L = {ww | where w is in (a + b)^*} (two identical parts) What regular expression should we intersect L with to get a^n b^m a^n b^m which is not CFL. ##Inter9* L is finite iff there exits no < [Show More]

Last updated: 1 month ago

Preview 1 out of 2 pages

Buy Now

Instant download

We Accept: