Question

1. Prove that {0n1n2n:n≥1} is not a regular language.
2. 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 would be represented as IIIII in unary notation. Show that each of the following is or is not a regular language.

(For regular languages, write down its regular expression or describe the automata accepting it; for languages that are not regular, prove it using pumping lemma)

1. {w: w is the unary notation for a number that is a multiple of 7}
2. {w: w is the unary notation for 10n,n ≥1}

Answer 1

A) Given Language L = {0ⁿ1ⁿ2ⁿ:n≥1}

Pumping Lemma states that

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

To prove that the language is not regular we have show that there exist alteast one string such that it is not in the language (i.e it has to fail pumping lemma Test

Let X=012∈ L (n=1) where the pumping length =3

we are spilting X into u ,v ,w such u = 0, v = 1 and w = 2

it satisfies all the conditions of the pumping lemma so it string which belong the language L

so here we will be pumping the v and see whether the obtained string is in language or not

if we find atleat one string which is not the language after pumping v then is the language won't be regular

and pumping v once (i.e i=2) then we get the string 01²2 which doesn't belong the given langugage L becuase it the condition that all the power of the 0,1,2 should be same

so the given language is not regular

B)  language is {w: w is the unary notation for a number that is a multiple of 7}

here we will give the NFA that accepts only the string of the language

The NFA contains 7 states where each state represents a remainder and possible remainder of a number when divided by 7 are {0,1,2,3,4,5,6}

so the given language is regular

C) language is {w: w is the unary notation for 10n,n ≥1}

this language contains of strings which are multiples of 10

is it similar to the above problem instead of 7 states the NFA Contains 10 states where the starting state is the intial and final state

so this language is also regular

Hope it is helpful for you. If so please upvote and for any queries please drop a comment :-)