Log In
2 votes

Please help in this question i think B and C also true

in Theory of Computation
edited by
Option c is wrong

it says ,string does not contain 11 as substring but this can be interpreted as it contains 101,which clearly machine doesn't accept
@ajay it says 11 substring not starting and ending 1 or two 1's
you didn't get the point, it fails to prove that 101,0101, or any other strings are not part of the language
it is true but not sufficient
But "11" substring means there is double ones come along correct me if i wrong ??
In option (b) and (c) all the strings that are specified by the language must be accepted

In option (c)  '1' and '0' are also the strings that don't contain '11' but these are not accepted by automata. so option c is incorrect.

in option (b) '101' is also a string that starts with 10 but it is not accepted by automata.

so (b) and (c) both are false
for b option u r right but how in C option 1 and 0 strings are accepted can u explain because there is no epsilon move suppose you are saying for 100 or 000 string so this don't contain 11 so it may be true @neeraj
option c says it accepts all strings that don't contain 11 as a substring, here we have '1' and '0'  the strings that don't  contain any 11 as substring so according to option c these also should be accepted by automata because these are not holding '11'  but these are not accepted at all  by the automata so option c is incorrect.

for the option, D says at least two 00 and almost one 1's.

my doubt is, string oo is valid for this option because at most means maximum occurrence of one is 1(either o times or 1 times), so string oo contain o occurrence of 1. string is valid???

Hira thakur.. String 00 is valid because.. See in the figure above q4 and q5 both are the final states..
Last Option is Right.

1 Answer

1 vote

Okk Before make answer, Let's carefully observer the question. Here we can see, given machine is DFA(M) .

Definition: So we have to know the definition of DFA for a particular language, which is states that language L must contain those strings which is accepted by machine M and also does not contain those strings which is reject by the machine M .

So here in the given DFA machine M , we can observe which actually string accepted and rejected by machine are following.

Note: Always start with small Strings to large possible strings.

Accepted strings: { 00, 000, 0000, 0000, ........, 001, 010, 100, 1000, 0100, 0010, 10000, ............}

Rejected Strings: { 010101, 100011, 001010, 01010,..........} Here many strings are possible I am writing some for options elimination purpose.

Now check options.

Option (A): Here more than 1's possible while our calculated accepted strings (above) set contains single 1. [FALSE].

Option (B): Every string start with 01, 00, 10. Means after 01 or 00 or 10 you can take any number of 1's which is not the part of accepted strings set. So [FALSE].

Option (C): doesn't contain the '11' as substrings, here this language does not saying that 101 strings doesn't accept ( it definitely accepted by option C language) since 101 does not accepted by accepted strings set. [FALSE].

Options (D): This is true because it full fill our requirements regarding given machine M. [TRUE].

Related questions

0 votes
1 answer
Let A be a NFA with epsilon transitions such that there are no transitions into q0 (start state) and no transitions out of qf (the accepting state). Let L be the language recognized by A. The above automata ‘A’ is modified by adding an epsilon-transition from Qf to Q0. The language accepted by the modified ‘A’ in terms of ‘L’ will be : Same as L Accepts null Accepts universal language Accept L+
asked Dec 2, 2017 in Theory of Computation badmetevils 1.3k views
0 votes
2 answers
How may Moore/Mealy m/c are possible with two states X & Y for the input alphabet {a, b} and output alphabet {0, 1} , where x is always the initial state?
asked Jan 6, 2019 in Theory of Computation prisonmatch 290 views
0 votes
2 answers
The difference between the number of states in minimal DFA and minimal NFA, which accepts all strings end with 3rd bit as b is _____. [ Assume $\sum$ = {a,b} ]
asked Sep 26, 2018 in Theory of Computation jhaanuj2108 223 views