Question

If A is a set of natural numbers and k is a natural number greater than 1, let

${\mathit{B}}_{\mathbf{k}}\left(A\right)\mathbf{=}\left\{w|wistherepresentationinbasekofsomenumberinA\right\}\mathbf{.}$

Here, we do not allow leading 0s in the representation of a number. For example $\mathbf{,}{\mathit{B}}_{\mathbf{2}}\left(\{3,5\}\right)\mathbf{=}\left\{11,101\right\}$and ${\mathit{B}}_{\mathbf{3}}\left(\{3,5\}\right)\mathbf{=}\left\{10,12\right\}\mathbf{.}$Give an example of a set A for which ${\mathit{B}}_{\mathbf{2}}\left(A\right)$is regular but${\mathit{B}}_{\mathbf{2}}\left(A\right)$ is not regular. Prove that your example works.

Short answer

$B_k\left(A\right)=\left\{w|wistherepresentationinbasekofsomenumberinA\right\}$is not regular is proved.

Step-by-step solution

Regular language.

A language is regular if it can be expressed in terms of regular expression.A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

Step 2:

$B_k\left(A\right)=\left\{w|wistherepresentationinbasekofsomenumberinA\right\}.$Here from the question the examples are given as,$,B_2\left(\{3,5\}\right)=\left\{11,101\right\}$,$B_3\left(\{3,5\}\right)=\left\{10,12\right\}.$not allow leading zeros and representation of number.

Let $[z{]}_3$be the number represented by the base-three numeral z. Since the set of numbers,

$A=\{2^n-1\mid n\in N\}$is represented in binary by the regular expression $1*1*$if we prove that,

$L=B_3\left(A\right)=\{z\in \{0,1,2\}*\mid n\in N.[z{]}_3=2^n-1\}\cap \{1,2\}\times \{0,1,2\}*$

is not regular.

Use the pumping lemma for regular languages. Suppose L is regular and is a word in L longer than the pumping length L . As such,

$$\begin{gathered} \left(a\right)\left|y\right|>0 \\ \left(b\right)\left|xy\right|⩽p,and \\ \left(c\right)\forall i>0,x{y}^{i}z\in L. \end{gathered}$$

$$\begin{gathered} L=\left\{a^n{b}^n{c}^n\right|n⩾0\} \\ z=uvwxy, \\ z=a^n{b}^n{c}^n\{n=1,z=abc\left\} \\ \right|z|=3n>n \end{gathered}$$

By applying pumping lemma to this grammar this grammar does not follow the property of pumping lemma and it is proved that this given language and its string$B_k\left(A\right)=\left\{w|wistherepresentationinbasekofsomenumberinA\right\}$is not regular language.