Q. If L is DFA-regular, L’ is

View solution

Q. Which of the following options is incorrect?

View solution

Q. Myphill Nerode does the following:

View solution

Q. Which of the following are related to tree automaton?

View solution

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