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

Chapter , Problem 1.71

(choose chapter or problem)

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

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.

Add to cart


Study Tools You Might Need

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back