Q. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?

View solution

Q. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______

View solution

Q. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L

View solution

Q. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?

View solution

Q. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.

View solution

Q. Which kind of proof is used to prove the regularity of a language?

View solution

Q. The language of balanced paranthesis is

View solution

Q. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.

View solution

Q. Which of the following is/are an example of pigeon hole principle?

View solution

Q. Pigeonhole principle can be applied in the following computer science algorithms:

View solution

Q. If n objects are distributed over m places, and n < m, then some of the places receive:

View solution

Q. Which of the following fields may have pigeonhole principle violated?

View solution

Q. Which of the following is not an application of Pumping Lemma?

View solution

Q. Which of the following can refer a language to be non regular?

View solution

Q. Which of the following is not an example of counting argument?

View solution

Q. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be ____________ under an operation op.

View solution

Q. Suppose a regular language L is closed under the operation halving, then the result would be:

View solution

Q. If L1′ and L2′ are regular languages, then L1.L2 will be

View solution

Q. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be

View solution

Q. If A and B are regular languages, !(A’ U B’) is:

View solution