StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q24E

Expert-verifiedFound in: Page 888

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.

**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 symbol**x**in it is represented by the set**x**;

**(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,}}...\).

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.

94% of StudySmarter users get better grades.

Sign up for free