Theory of Computation from \" an introduction to formal languages and automata 6

Question

Theory of Computation

from " an introduction to formal languages and automata 6th edition "

Solve these questions as marked below.

Please give a clear answer with all the needed steps as what was mentiond in the book.

use KEYBOARD instead of written by hand.

5. Do Exercise 6(b) of Section 4.3 at page 126 6. Determine whether or not the following languages on a are regular: (a) L la n 2, is a prime number b) L {a" n is not a prime number t. (c) L ta" n ks for some k 20h d) L ta" n 2 for some k 0 e) L ta" n is the product of two prime numbers (f) L ta" n is either prime or the product of two or more prime numbers (g) L where L is the language in part (a)

Explanation / Answer

(b) Given language is not regular.

Explanation : Using Pumping Lemma we can prove it.

Suppose n is product of two prime number which is not prime( Prime number is divisible by itself and 1 only)

Hence w= ap.q

p.q >=m

w can be decomposed into xyz where |xy| <= m and y is not null. Suppose y = ak

where 1<=k<=m then we pump i times to generate a string that contains p.q+k.(i-1) a's

Let i = 1+p.q then p.q+k((1+p.q)-1) = pq+k.pq = p.q.(k+1).

Since p.q(k+1) can not be a product of two primes ap.q(k+1) does not belongs to L.

Thus L is not regular.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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