The Gateway to Computer Science Excellence
+2 votes

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

in Theory of Computation by Boss (11.7k points)
edited by | 306 views
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].

by Active (2k points)

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,737 questions
57,390 answers
105,443 users