Register

Introduction to theory of computing by "Michael sipser" 3rd edition page no:37

• edited by
5,003 views
3 votes
3 votes

A minimal DFA diagram for the language A = {w| w contains at least one 1 and an even number of 0s follow the last 1}?

• edited by
User Avatar

6 Answers

Best answer
4 votes
4 votes

DFA

Note : last 1 followed by even number of 0 does not mean 0 cannot come before 1.

Some example of strings, 01,0100, 101, 10100.

• selected by
User Avatar
0 votes
0 votes
User Avatar
0 votes
0 votes
We need minimum 5 states for this .

(The verified answer is wrong , it is not accepting 101 or 10100 )
User Avatar
Page:
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
zshaikh asked May 10, 2023
223 views
Exercise 1.30 from the textbook "Introduction to the Theory of Computation" by Michael Sipser (3rd edition).
For the following regular expression:a+|(ab)+Over the alphabet:{a,b}Give an epsilon-NFA that recognizes the same language.
User Avatar
3 votes
3 votes
1 answer
2
jaiganeshcse94 asked Jul 28, 2016
674 views
Introduction to languages and the theory of computing by "john c martin" page no. 48
A minimal DFA for language L={x∈{a, b}* | x ends with 'b' and does not contain the substring 'aa'}?
A minimal DFA for language L={x∈{a, b}* | x ends with 'b' and does not contain the substring 'aa'}?
User Avatar
0 votes
0 votes
1 answer
3
admin asked Apr 28, 2019
963 views
Michael Sipser Edition 3 Exercise 1 Question 37 (Page No. 89)
Let $C_{n} = \{x| x \text{ is a binary number that is a multiple of $n$}\}.$ Show that for each $n\geq1,$ the language $C_{n}$ is regular$.$
Let $C_{n} = \{x| x \text{ is a binary number that is a multiple of $n$}\}.$ Show that for each $n\geq1,$ the language $C_{n}$ is regular$.$
User Avatar
0 votes
0 votes
3 answers
4
anumita asked Jun 6, 2017
3,676 views
michael sipser chp 1, 3rd edition, Q 12 , dfa
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab } give a DFA with Five states that recognizes D and a regular expression that generates D.
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab }give a DFA with Five states that recognizes D and a regular express...
User Avatar
Link Copied!