[Solved] Two strings x and y are indistinguishable if:

Computer Science Engineering (CSE)
Theory of Computation
Unit 1
Two strings x and y are indistinguishabl...

Q.	Two strings x and y are indistinguishable if:
A.	δ(s, x) = δ (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
B.	if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A
C.	Both above statements are true
D.	None of the above
Answer» C. Both above statements are true

View all MCQs in: Theory of Computation

Discussion

Related Questions

Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called
Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?
The set strings of 0's and 1's with atmost one pair consecutive one's-
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
Which of the following strings is not generated by the following grammar? S → SaSbS ε
A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :
Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :
Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.