Theory of Computing > QUESTIONS & ANSWERS > CS 421 Theory of computing HW2D – RG, Pumping Lemma and Closures for Regular Languages (based on w (All)

CS 421 Theory of computing HW2D – RG, Pumping Lemma and Closures for Regular Languages (based on week7) | California State University, San Marcos

Document Content and Description Below

California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii – HW2D – RG, Pumping Lemma and Closures for Regular Languages (based on week7) =======================... ============================================================ DUE: Week 8 Friday before midnight TOTAL: 15 pts ** Name: **Qian Zhu ======================== Review Questions: [4 pts] ======================== A. Convert the following FA Trs’s into a Regular Grammar. Use non-terminals V0, V1, etc. [2] B. My FA has N states. ================================================= Proofs by Contradiction [1pt per prompt = 11 pts] ================================================== 1. Prove that L = {0^x 1^y 0^x+y | x >= 1 and y >=1} is not Regular. Must use the Pumping Lemma. [7pts] [ HINT: Describe the language in English first. ] v has to be where o Where v is: o Repeat factor i= o What does uv^iw look like? o Is uv^iw in L? Thus, there was no way to break S into uvw and repeat or skip v as much as we want. We found a counter example S. 4) Conclusion about L: 2. Prove that L = {0^x 1^y 2^x+y | x >= 0 and y >=1} is not Regular. Must use Closure(s). [3 pts] [ HINT: Describe the language in English first ] Hint: Your "destination" should be Describe Operation Result End with {a^z b^z} which is not regular - Conclusion about L with a reason: 3. L1 is unknown L2 is regular L1L2 is regular. Thus I think L1 is regular. -- What is wrong with my reasoning? [1pt] [Show More]

Last updated: 1 month ago

Preview 1 out of 3 pages

Buy Now

Instant download

We Accept: