can I get help for (a,d,f) please? 2.4.3. Show that each of the following is or

Question

can I get help for (a,d,f) please?

2.4.3. Show that each of the following is or is not a regular language. The decimal notation for a number is the number written in the usual way, as a string over the alphabet (0, 1,. ..,9). For example, the decimal notation for 13 is a string of length 2. In unary notation, only the symbol I is used; thus 5 (a) fw : w is the unary notation for a number that is a multiple of 7) (b) fw w is the decimal notation for a number that is a multiple of 7) (c) fw : w is the unary notation for a number n such that there is a pair p, p +2 of twin primes, both greater than ny (d) fw: w is, for some n 2 1, the unary notation for 10) (e) (w : w is, for some n 2 1, the decimal notation for 10") (f) tw: w is a sequence of decimal digits that occurs in the infinite decimal expansion of 1/7) (For example, 5714 is such a sequence, since 1/7 0.14285714285714...)

Explanation / Answer

a) L is regular since it can be described by the regular expression (1111111)*

d) L is not regular as because any machine accepting L would have to count 1s. Proof of this is the pumping lemma - Let w = 1^P , N ? P and P is a power of 10. the number of 1s can be atmost P.When we pump it in once, we obtain a string whose maximum length is 2P but as the next power of 10 is 10P so s cannot be in L.

f)L is regular as 1/7 is a repeating fraction as the 142857 keeps on repeating itself so the number of repeating decimals is finite.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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