• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q24E

Expert-verified Found in: Page 888 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that the set $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ is not regular using the pumping lemma from Exercise 22.

The set $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ is not regular is proved as true.

See the step by step solution

## Step 1: General form

Finite-state automaton (Definition):A finite-state automata $${\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)$$ consists of an initial or start state $${{\bf{s}}_0}$$, a finite set S of states, a finite alphabet of inputs I, a transition function f that assigns a future state to each pair of state and input (such that $${\bf{f:S \times I}} \to {\bf{S}}$$), and a subset F of S made up of final states (or accepting states).

Regular expressions (Definition):A recursive definition of the regular expressions over a set I is as follows:

The symbol $$\emptyset$$ is a regular expression;

The symbol $${\bf{\lambda }}$$is a regular expression;

whenever $${\bf{x}} \in {\bf{I}}$$; the symbol x is a regular expression.

When A and B are regular expressions, the symbols $$\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}$$ and $${\bf{A*}}$$ are also regular expressions.

Regular sets are the sets that regular expressions represent.

Theorem 2:A set is formed by a regular grammar if and only if it is a regular set.

Rules of regular expression represents a set:

$$\emptyset$$ represents the string-free set, or the empty set;

$${\bf{\lambda }}$$ represents the set $$\left\{ {\bf{\lambda }} \right\}$$, which is the set containing the empty string;

The string having the symbolxin it is represented by the setx;

(AB) depicts the order of the sets that are represented by both A and B;

The combination of the sets that both A and B represent is represented by $$\left( {{\bf{A}} \cup {\bf{B}}} \right)$$;

The Kleene closure of the sets that A represents is represented by $${\bf{A*}}$$.

Pumping lemma: If $${\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)$$ is a deterministic finite-state automaton and if x is a string in $${\bf{L}}\left( {\bf{M}} \right)$$, the language recognized by M, with $${\bf{l}}\left( {\bf{x}} \right) \ge \left| {\bf{S}} \right|$$, then there are strings u, v, and w in $${\bf{I*}}$$ such that $${\bf{x = uvw,l}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|$$ and $${\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}$$, and $${\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)$$ for $${\bf{i = 0,1,2,}}...$$.

## Step 2: Proof of the given statement

Given that, $${\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)$$ be a deterministic finite-state automaton and $${\bf{L}}\left( {\bf{M}} \right)$$ is language recognized by $${\bf{M}}$$.

Refer pumping lemma to prove the given statement.

To prove: the set $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ is not regular.

Proof:

For the sake of conflict, let's assume that $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ is a regular.

Since $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ is a regular, $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$ can be produced by a deterministic finite-state automaton $${\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)$$.

Let $${\bf{k = }}\left| {\bf{S}} \right|$$.

$$\begin{array}{c}{\bf{l}}\left( {{{\bf{1}}^{{{\bf{k}}^2}}}} \right){\bf{ = }}{{\bf{k}}^2}\\{\bf{ = }}{\left| {\bf{S}} \right|^2}\\ \ge \left| {\bf{S}} \right|\end{array}$$

As a result of the pumping lemma, strings u, v, and w in $${\bf{I*}}$$ exist such that $${\bf{x = uvw,L}}\left( {{\bf{uv}}} \right) \le \left| {\bf{S}} \right|$$ and $${\bf{l}}\left( {\bf{v}} \right) \ge {\bf{1}}$$, and $${\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)$$ for $${\bf{i = 0,1,2,}}...$$.

Let v be a collection of positive integers m, so that $${\bf{v = }}{{\bf{1}}^{\bf{m}}}$$.

But M also produces $${{\bf{1}}^{{{\bf{n}}^{\bf{2}}}{\bf{ - m}}}}{{\bf{1}}^{{\bf{pm}}}}$$ for all p is positive integers (as $${\bf{u}}{{\bf{v}}^{\bf{i}}}{\bf{w}} \in {\bf{L}}\left( {\bf{M}} \right)$$). Since $${{\bf{1}}^{{{\bf{n}}^{\bf{2}}}{\bf{ - m}}}}{{\bf{1}}^{{\bf{pm}}}}{\bf{ = }}{{\bf{1}}^{{{\bf{n}}^{\bf{2}}}{\bf{ + }}\left( {{\bf{p - 1}}} \right){\bf{m}}}}$$, it follows that for any positive integers p, $${{\bf{n}}^{\bf{2}}}{\bf{ + }}\left( {{\bf{p - 1}}} \right){\bf{m}}$$ is a perfect square.

This is impossible because, at some point, one of the elements in $${{\bf{n}}^{\bf{2}}}{\bf{ + }}\left( {{\bf{p - 1}}} \right){\bf{m}}$$ is not a perfect square because the difference between succeeding perfect squares grows steadily as the difference between succeeding terms $${{\bf{n}}^{\bf{2}}}{\bf{ + }}\left( {{\bf{p - 1}}} \right){\bf{m}}$$ grows steadily by m. Consequently, a contradiction has been found.

As a result, it follows that our presumption that “$$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$is regular" is false and that $$\left\{ {{{\bf{1}}^{{{\bf{n}}^2}}}\left| {{\bf{n = 0,1,2,}}...} \right.} \right\}$$is not regular.

Hence, the statement is proved as true. ### Want to see more solutions like these? 