Suppose that L is any language, not necessarily regular, ... !! Exercise 4.2.10:

Question

Suppose that L is any language, not necessarily regular, ...

!! Exercise 4.2.10: Suppose that L is any language, not necessarily regular, whose alphabet is 10j; i.e., the strings of L consist of 0's only. Prove that L* is regular. Hint: At first, this theorem sounds preposterous. However, an example will help you see why it is true. Consider the language L 0is prime], which we know is not regular by Example 4.3. Strings 00 and 000 are in L, since 2 and 3 are both primes. Thus, if j 2 2, we can show 0 is in L*. If j is even, use j/2 copies of 00, and if j is odd, use one copy of 000 and (j - 3)/:2 copies of 00. Thus, L*000

Explanation / Answer

Lets consider the generic case where L={0^i | i is an integer }

This means that strings 00 and 000 are in L ( considering the generic case)

By the logic in the question, 0^j is in L* if j>=2

If j=1 , 0 is still in L*

Hence L* is regular for all scenarios.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.