The Gateway to Computer Science Excellence
+3 votes
150 views
create a dfa with odd occurrence of sub string "abb" .and short cut for finding no.of states
in Theory of Computation by
edited by | 150 views
0
i think it needs minimum 7 state....?
0
can u explain it.plz
0

minimum no. of states required = 6

@all mix  what is answer given btw

0
i think it should be 6...i do not have answer
0

there is as of now no shortcut to find minimum no. of states required 

Thank you !

1 Answer

+4 votes
Best answer

6 will be answer 

by Boss
selected by
0

sumit goyal 1

abab....is also accepted by given DFA which is invalid....

0

now check  hs_yadav

0
perfect....
0
thanks for pointing mistake
0
there is small mistake, otherwise your DFA is perfect.

6th state(clockwise from initial state) will have transition to 5th state(clockwise from initial state) on seeing 'a'
0

joshi_nitish   can you tell any string in which dfa fails

0
your DFA is not accepting $abbabab$, which is in language
0
edited thanks for pointing mistake
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,951 answers
201,132 comments
118,172 users