Let = {0,1}. a. Let A = {0ku0k| k 1 and u }. Show that A is regular. b. Let B = {0k1u0k| k 1 and u }. Show that B is not regular.

1.71

Let .

a. Let . Show that A is regular.

b. Let . Show that B is not regular.

Step By Step Solution

Step 1 of 2

a.

(Here, u belongs to, 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 is the start state and 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 .

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