Theory of Computing > QUESTIONS & ANSWERS > California State University, San Marcos CS 421 Theory of computing CS421 - Yoshii – HW2D – RG,  (All)

# 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

OR

OR

## Reviews( 0 )

### \$9.00

Can't find what you want? Try our AI powered Search

OR

69
0

### Document information

Connected school, study & course

Nov 15, 2022

Number of pages

3

Written in

#### Seller

##### Kirsch

Member since 4 years

898 Documents Sold

This document has been written for:

Nov 15, 2022

0

Views

69

## THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

#### Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.

\$9.00