### Solution Found!

# 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. }\)

### Questions & Answers

**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. }\)

**ANSWER:**

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.