Let $\mathbf{\Sigma }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}\mathbf{.}$

a. Let $\mathbf{A}\mathbf{=}\mathbf{\{}{\mathbf{0}}^{\mathbf{k}}\mathbf{u}{\mathbf{0}}^{\mathbf{k}}\mathbf{k}\mathbf{\ge }\mathbf{1}\mathbf{}\mathbf{and}\mathbf{}\mathbf{u}\mathbf{\in }{\mathbf{\Sigma }}^{\mathbf{*}}\mathbf{\}}$Show that $\mathbf{A}$is regular.

b. Let $\mathbf{B}\mathbf{=}\mathbf{\left\{}{\mathbf{0}}^{\mathbf{k}}\mathbf{1}\mathbf{u}{\mathbf{0}}^{\mathbf{k}}\mathbf{\right|}\mathbf{k}\mathbf{\ge }\mathbf{1}\mathbf{}\mathbf{and}\mathbf{}\mathbf{u}\mathbf{\in }\mathbf{\Sigma }\mathbf{*}\mathbf{\}}$Show that$\mathbf{B}$ is not regular.

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.

a).

For the string which contains$\mathrm{\Sigma }=\{0,1\}$ where string can be made for the given language in the question and string is formed.

And for the given grammar the language is possible and also its string can be formed and also deterministic finite machine is possible.

The string formed is given as,

In regular expression,

$0(0+1)*0$

Here, this isbecause$(0+1)*$ can generate all the string required,

$(0+1)*=0(0+1)*0=00(0+1)*00=0^{\mathrm{n}}(0+1)*0^{\mathrm{n}}$

Hence, This is proved that $\mathrm{A}=\{0^{\mathrm{k}}\mathrm{u}{0}^{\mathrm{k}}\mathrm{k}\ge 1\mathrm{and}\mathrm{u}\in {\mathrm{\Sigma }}^{*}\}$is regular. And this is a regular language and deterministic finite machine is possible.

b).

For the string which contains$\mathrm{\Sigma }=\{0,1\}$ where 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.

For the given language,$\mathrm{B}=\left\{0^{\mathrm{k}}1\mathrm{u}{0}^{\mathrm{k}}\right|\mathrm{k}\ge 1\mathrm{and}\mathrm{u}\in \mathrm{\Sigma }*\}.$

$\mathrm{B}=\left\{0^{\mathrm{k}}1\mathrm{u}{0}^{\mathrm{k}}\right|\mathrm{k}\ge 1\mathrm{and}\mathrm{u}\in \mathrm{\Sigma }*\}.$

The deterministic finite automata is not possible.

Hence,$\mathrm{B}=\left\{0^{\mathrm{k}}1\mathrm{u}{0}^{\mathrm{k}}\right|\mathrm{k}\ge 1\mathrm{and}\mathrm{u}\in \mathrm{\Sigma }*\}.$ is not regular. This is not a regular language and no deterministic finite machine is possible.