# MadeEasy Test Series 2018: Theory Of Computation - Finite Automata

404 views

edited
0
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
0
@ajay it says 11 substring not starting and ending 1 or two 1's
0
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
0
But "11" substring means there is double ones come along correct me if i wrong ??
0
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
0
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
0
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.
0

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???

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

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.

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

1
1.3k views
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+
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} ]