Question

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.

Short answer

a) $\mathrm{A}$ is regular is proved.

b) $\mathrm{B}$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.

Language is regular.

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.

Language is not regular.

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.