Question:

a. Let $\mathit{B}\mathbf{=}\mathbf{\left\{}{\mathbf{1}}^{\mathbf{k}}\mathit{y}\mathbf{\right|}\mathit{y}\mathbf{\in }{\left\{0,1\right\}}^{\mathbf{*}}$and $\mathit{y}\mathbf{}\mathit{c}\mathit{o}\mathit{n}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathit{s}\mathbf{}\mathit{a}\mathit{t}\mathit{l}\mathit{e}\mathit{a}\mathit{s}\mathit{t}\mathbf{}\mathit{k}\mathbf{1}\mathit{s}\mathbf{,}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathit{k}\mathbf{⩾}\mathbf{1}\mathbf{\}}\mathbf{.}$ Show that B is a regular language.

b. Let $\mathit{C}\mathbf{=}\mathbf{\left\{}{\mathbf{1}}^{\mathbf{k}}\mathit{y}\mathbf{\right|}\mathit{y}\mathbf{\in }{\left\{0,1\right\}}^{\mathbf{*}}$ and $\mathit{y}\mathbf{}\mathit{c}\mathit{o}\mathit{n}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathit{s}\mathbf{}\mathit{a}\mathit{t}\mathit{m}\mathit{o}\mathit{s}\mathit{t}\mathbf{}\mathit{k}\mathbf{1}\mathit{s}\mathbf{,}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathbf{}\mathit{k}\mathbf{⩾}\mathbf{1}\mathbf{\}}\mathbf{.}$ Show that C isn’t a 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.

The pumping lemma for regular languages $B=\left\{1^{k}y\right|y^I{\left\{0,1\right\}}^{*}$} is only a tool for showing that a language is not regular; it cannot be used to show that a language is regular. The two most straightforward ways to demonstrate that a language is regular are one to write a regular grammar that generates it, and two to design a finite state automaton that recognizes it.

Fig: Deterministic finite automata for language

It’s not at all hard to design a regular grammar that generates this language, or a finite state machine that recognizes it.

b).

Suppose C is a regular language. Let p be the pumping length given by the pumping lemma.

Let $s=1^p{01}^p$

Because $s\in Cand\left|s\right|⩾p,$

by the pumping lemma we can split s into three pieces

$s=xyzsuchthatfori⩾0xyiz\in C.$

$$\begin{gathered} \left|xy\right|⩽pand \\ \left|y\right|\ge 0 \end{gathered}$$

By the pumping lemma, y must consist of ones. The string xz results in fewer ones before the zero than after. Thus d will always have more than $k1s,sos/\in C$. This violates the pumping lemma, therefore is not regular.

Hence, Cis nota regular language is proved.