Question

Use Exercise 29 to show that the language consisting of all bit strings that are palindromes (that is, strings that equal their own reversals) is not regular.

Short answer

Therefore,the language consisting of all bit strings that are palindromes is not regularis proved as true.

Step-by-step solution

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 subsequent state to each pair of states and inputs (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:

A regular expression is the symbol \(\emptyset \);

A regular expression is the symbol \({\bf{\lambda }}\);

When \({\bf{x}} \in {\bf{I}}\) occurs, 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.

Kleene’s theorem:A finite-state automaton must recognise a set-in order for it to be considered regular.

Theorem 2:If and only if it is a regular set, a set is produced by a regular grammar.

Concept of distinguishable with respect to L:

Suppose that L is a subset of \({\bf{I*}}\), where \({\bf{I}}\) is a nonempty set of symbols. If \({\bf{x}} \in {\bf{I*}}\), let \(\frac{{\bf{L}}}{{\bf{x}}}{\bf{ = }}\left\{ {{\bf{z}} \in {\bf{I*}}\left| {{\bf{xz}} \in {\bf{L}}} \right.} \right\}\). If \(\frac{{\bf{L}}}{{\bf{x}}} \ne \frac{{\bf{L}}}{{\bf{y}}}\), thenthe strings \({\bf{x}} \in {\bf{I*}}\) and \({\bf{y}} \in {\bf{I*}}\) can be distinguished from one another with respect to L. A string z is said to distinguish x and y with respect to L if \({\bf{xz}} \in {\bf{L}}\) but \({\bf{yz}} \notin {\bf{L}}\), or \({\bf{xz}} \notin {\bf{L}}\), but \({\bf{yz}} \in {\bf{L}}\).

Concept of indistinguishable with respect to L:

If\(\frac{{\bf{L}}}{{\bf{x}}}{\bf{ = }}\frac{{\bf{L}}}{{\bf{y}}}\), then x and y are said to be indistinguishable from L.

Step 2: Proof of the given statement

Given that,use Exercise 29.

Referring to Exercise 29: every deterministic finite-state automaton recognizing L has at least n states.

To prove: The language composed of all bit strings that are palindromes (i.e., strings that map to their own inverses) is not regular.

Proof:

Let x and y be two distinct palindromes. Then, x and y are also distinguishable with respect to P (as \({\bf{x}}{{\bf{x}}^{\bf{R}}} \in {\bf{P}}\) while \({\bf{y}}{{\bf{x}}^{\bf{R}}} \notin {\bf{P}}\), which implies \(\frac{{\bf{P}}}{{\bf{x}}} \ne \frac{{\bf{P}}}{{\bf{y}}}\) as \({{\bf{x}}^{\bf{R}}} \in \frac{{\bf{P}}}{{\bf{x}}}\) while \({{\bf{x}}^{\bf{R}}} \notin \frac{{\bf{P}}}{{\bf{y}}}\)).

Let us assume that the \({2^{\bf{n}}}\)different strings of length n.

A deterministic finite-state automaton for identifying palindromes will then need at least \({2^{\bf{n}}}\)states as each of these strings is then distinct with regard to P.

The deterministic finite-state automaton for recognizing palindromes, however, needs at least \({2^{\bf{n}}}\)states for all positive integers n because the value of n is an arbitrary positive integer. But this is impossible since a deterministic finite-state automaton cannot have an unlimited number of states, hence such an automaton cannot exist.

The language made up entirely of bit strings that are palindromes is not regular since there is no deterministic finite-state automaton that can recognize them all.

Hence, the statement is proved as true.