Q. Given languages:
i) {a^nb^n|n>=0}

ii) <div>n</div>n

iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences

Which of the following is/are non regular?

View solution

Q. Finite state machine are not able to recognize Palindromes because:

View solution

Q. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.

View solution

Q. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.

View solution

Q. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?

View solution

Q. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?

View solution

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