The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
117 views
create a dfa with odd occurrence of sub string "abb" .and short cut for finding no.of states
in Theory of Computation by (83 points)
edited by | 117 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 (10.5k points)
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

Related questions

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
50,339 questions
55,765 answers
192,354 comments
90,815 users