Let = {0,1}. a. Let A = {0ku0k

Chapter , Problem 1.71

(choose chapter or problem)

QUESTION:

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

a. $$\text { Let } A=\left\{0^{k} u 0^{k} \mid k \geq 1 \text { and } u \in \Sigma^{*}\right\} \text {. Show that } A \text { is regular. }$$
b. $$\text { Let } B=\left\{0^{k} 1 u 0^{k} \mid k \geq 1 \text { and } u \in \Sigma^{*}\right\} \text {. Show that } B \text { is not regular. }$$

QUESTION:

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

a. $$\text { Let } A=\left\{0^{k} u 0^{k} \mid k \geq 1 \text { and } u \in \Sigma^{*}\right\} \text {. Show that } A \text { is regular. }$$
b. $$\text { Let } B=\left\{0^{k} 1 u 0^{k} \mid k \geq 1 \text { and } u \in \Sigma^{*}\right\} \text {. Show that } B \text { is not regular. }$$

Step 1 of 2

a.  $$A=\left\{0^{k} u 0^{k} \mid k \geq 1 \text { and } u \epsilon \Sigma^{*}\right\}$$

(Here, u belongs to $$\Sigma^{*}$$, so it can take all the zeros of both sides leaving just single 0 in start and at end. So it is the language of all strings starting and ending with 0. )

We can easily construct a DFA that accepts all the strings of the given language. The DFA corresponding to A is given below:

This DFA consists of 4 states where $$q_{0}$$ is the start state and $$q_{3}$$ is the final state. The given DFA will accept all strings that are accepted by A.

This will accept the strings that will starts and ends with 0 and in between $$(0,1)^{*}$$.

Thus a finite automaton recognizes the language. Hence the language is regular.