TOC 1.4 (pp. 77-82) Pumping Lemma
- Due Oct 22, 2021 by 11:59pm
- Points 15
- Submitting a file upload
- File Types pdf
Goal
Prove a language regular or nonregular using the Pumping Lemma.
Task
Use the pumping lemma to prove the following languages are irregular. If it turns out a min p is holding and you think it is regular, explain why that min p works (i.e. suggest a DFA but not required to draw). Show your work by using the table guide here and explain your finding with your completed table (also see lecture). Alternatively, you may go the only-proof route if you like with a different set of problems (below).
1. A language where the amount of 1's in a string is a square of n, n >= 0. Examples:
n=0, ""
n=1, 1
n=2, 1111
n=3, 111111111
2. A language of zeros followed by ones where the amount of 0's is always more than the amount of 1's. Examples:
0
001
0001
00011
3. xwr where x=(0,1) w=(0,1)* and r = whatever wasn't picked for x. Create a few examples.
Alternate Task: Purely Proofs
In leu of the problems above, you may complete the direct-proof route if it is more intuitive to you with these problems. Show your work, and as above explain your finding. Math notation alone is not sufficient.
- Page 89: Problem 1.35
- Page 90: Problem 1.46 c
- Page 91: Problem 1.55 h
Submission
PDF only. Please turn in the assignment in Canvas.