×
Log in to StudySoup
Get Full Access to Introduction To The Theory Of Computation - 3 Edition - Chapter 1 - Problem 1.71
Join StudySoup for FREE
Get Full Access to Introduction To The Theory Of Computation - 3 Edition - Chapter 1 - Problem 1.71

Already have an account? Login here
×
Reset your password

Let = {0,1}. a. Let A = {0ku0k| k 1 and u }. Show that A

Introduction to the Theory of Computation | 3rd Edition | ISBN: 9781133187790 | Authors: Michael Sipser ISBN: 9781133187790 221

Solution for problem 1.71 Chapter 1

Introduction to the Theory of Computation | 3rd Edition

  • Textbook Solutions
  • 2901 Step-by-step solutions solved by professors and subject experts
  • Get 24/7 help from StudySoup virtual teaching assistants
Introduction to the Theory of Computation | 3rd Edition | ISBN: 9781133187790 | Authors: Michael Sipser

Introduction to the Theory of Computation | 3rd Edition

4 5 1 410 Reviews
21
4
Problem 1.71

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.

Step-by-Step Solution:

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.

Step 2 of 2

Chapter 1, Problem 1.71 is Solved
Textbook: Introduction to the Theory of Computation
Edition: 3
Author: Michael Sipser
ISBN: 9781133187790

Other solutions

People also purchased

Related chapters

Unlock Textbook Solution

Enter your email below to unlock your verified solution to:

Let = {0,1}. a. Let A = {0ku0k| k 1 and u }. Show that A