GATE PYQ

Theory of Computation

Q181.
Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

Q182.
Let R_{1} and R_{2} be regular sets defined over the alphabet, then

Q183.
Let L_{1}=\{w \in \{0,1\}|w has at least as many occurrences of (110)'s as (011)'s}. Let L_{2}=\{w \in \{0,1\}|w has at least as many occurrence of (000)'s as (111)'s}. Which one of the following is TRUE?

Q184.
Choose the correct alternatives (More than one may be correct).Recursive languages are:

Q185.
Which of the following languages is (are) non-regular? L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\} L_2 = \{w \mid w reads the same forward and backward\} L_3 = \{w \in \{0, 1\} ^* \mid w contains an even number of 0's and an even number of 1's\}

Q186.
S\rightarrowaSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

Q187.
What is the highest type number that can be assigned to the following grammar?S \rightarrow A a, A \rightarrow B a, B \rightarrow a b c

Q188.
Consider the regular grammar below S \rightarrow bS \mid aA \mid \epsilon A \rightarrow aS \mid bA The Myhill-Nerode equivalence classes for the language generated by the grammar are

Q189.
Consider the following grammar G: Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G)\subseteq \{a,b\}^{+} generated by G is

Q190.
Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE?