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

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 year ago

Preview 1 out of 3 pages