Hello, I need help in solving the highlighted question . It\'s from \" Introduct

Question

Hello,

I need help in solving the highlighted question. It's from "Introduction to Formal languages and automata - 6th edition by Peter Linz".

*** Please show the steps, solve it BRIEFLY, and provide a clear picture of the solution.

6. Determine whether or not the following languages on 3 a are regular: (a) L {a" n 2 2, is a prime number (b) L fan n is not a prime number (c) L tan n ks for some k 20h (d) L ta" n 2 for some k 0 (e)L {a" n is the product of two prime numbers (f) L fan 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

In order to show that given language L is not a regular language using the pumping lemma, you must construct a string wL which cannot be pumped in the manner germane to regular languages. In this case, the goal is to show that pumping some string wL will generate a string the length of which is composite. Here is a relatively simple proof using the pumping lemma.

Suppose that L is regular. Since L is regular, there exists a DFA M with k states such that, for every string zL such that klen(z), z can be decomposed into substrings uvw such that len(uv)k, 0<len(v), and uviwL for all i0.

Let n be a prime number. Since n is prime, the string an is a member of L. Since an is a member of L, an can be decomposed into substrings uvw satisfying the conditions of the pumping lemma. In particular, uvn+1w must be a member of L. However, len(uvn+1w) is not prime:
len(uvn+1w)=len(uvnvw)
   =len(uvw)+len(vn)
   =n+n.len(v)
   =n(1+len(v))
Since n(1+len(v)) is composite, its length is not prime. Therefore, uvn+1w is not a member of L, a contradiction. Therefore, L is not a regular language.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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