Question

Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma

a) {a^p | p is a prime number}

b) {xax | x Î{a,b}^*} (start by listing some strings in, not in, the language

Answer 1

Solution ::

Given language L is regular if we can draw a finite automata or give a regular expression or a regular grammar to L.

a- is the regular expression for given language.Hence regular

d- is the regular expression for given language.Hence regular

j-is the regular expression for given language.Hence regular

pumping lemma:

For any regular language L, there exists an integer k, such that for all x ∈ L with |x| ≥ k, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ k
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw ∈ L

if a language doesnot satisfy pumping lemma properties, then it is not a regular language.

b--let the language is regular, then there is a constant k>0 and let where x=uvw.

As ,it means that for some .and

Now if we pump v, then (i.e,uvvw),then which doesn't belong to language since .

Hence this is violating the 3rd condition of pumping lemma.Hence not regular.

one can also prove that this is not regular in other way.

first we have to count number of a's and make sure that,number of b's is double the number of a's.

Hence we need stack to do that.in stack,for every a in input,we push 2a's and for every b in input ,we pop one 'a ' from top of stack.if the stack is empty by the end of input, we can say that word belongs to language.

Here no stack is available in Finite automata,we need push down automata for that.Hence this is not a regular.(This is a non formal approach).

e-let the language is regular, then there is a constant k.let where p is a prime number>k.

We don't know the decomposition of x into uvw, but since |uv| k, it follows that |w| > 1. As usual, |v| > 0.

let i = |uw|. Then |uvⁱw|= |uw| + |v||uw| = (1 + |v|)|uw|. Since (1 + |v|) and |uw| are each greater than 1, the product must be a composite number. Thus |xyⁱz| is a composite number.

There fore it is not a prime and hence,it doesn't belong to language.

Therefore third condition of pumping lemma is violated.

Hence not a regular language.

Thank you::::