FOR FREE MATERIALS

Subject Mock

Example:

Q. $L = {a^{i^{2}}, i \geq 1}$ is not a regular language.

Solutions:

Initially, we always assume that it is regular language and the machine is DFA.

Let n is no. of state at DFA which accepts Language.

Now decompose it by xyz with two conditions.

Here,

Now we are going to check,

This time we check for ${xy}^{2} z \in L$ .

So, we can say,

Also | x | + | y | + | z | < | x | + 2| y | + | z | hence, | y | > 0 (true) or | y | ≥ 1 and | xy | ≤ n satisfy.

Now we can say,

| xy | ≤ n, | y | > 0 or | y | ≥ 1 then we can say | y | ≤ n because | xy | ≤ n.

Then we can say,

Now we can add (n + 1) on left-hand side of $| {xy}^{2} z |$ then we can say,

Now looks at the given language $L = {a^{i^{2}}, i \geq 1}$ from language it is clear that every string ω which belongs to the language is a length of $i^{2}$ (perfect square).

So if $ω = a^{n^{2}}$ then next string $ω = a^{{(n + 1)}^{2}}$ here $n^{2}$ and ${(n + 1)}^{2}$ is perfect square.

But length of string ${xy}^{2} z$ is between $n^{2}$ and ${(n + 1)}^{2}$ i.e. $n^{2} < | {xy}^{2} z | < {(n + 1)}^{2}$ .

So, it is clear that $| {xy}^{2} z |$ is not perfect square because between two perfect square no perfect square is possible like here $n^{2}$ and ${(n + 1)}^{2}$ are both perfect squares so,

Like $3^{2} = 9,$ $4^{2} = 16$ between 9 and 16 no perfect square is possible.

So, ${xy}^{2} z$ string violating pumping lemma, so, $L = {a^{i^{2}}, i \geq 1}$ violet pumping lemma and it is not Regular Language.

Please Login to Bookmark