1) Context free Grammar is ? a. A Compiler b. A language expression c. A regular expression d. None of these Answer = B Explanation: Context free Grammar generate the context free languages. These are defined by the rule of the form A -> b Where A a non […]
The basic limitation of an FSM is that a) it does not have the capability to remember information b) it sometimes recognizes grammars that are not regular c) it sometimes fails to recognize grammars that are regular d) all of the above Ans is a 2. Palindromes can’t be […]
Given the language L-{ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa 1,2 and 3 2,3 and 4 1,2 and 4 1,3 and 4 _____________________________________________________________________________________ 2. Push down machine represents Type 0 […]
1) S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of (A) All palindromes. (B) All odd length palindromes. (C) Strings that begin and end with the same symbol (D) All even length palindromes. Answer (B) The strings […]
1. Which of the following pairs have different expressive power? a) DFA AND NDFA b) DPDA AND NPDA c) Deterministic single tape turing machine and Non-Deterministic single tape turing machine d) single tape turing machine and multiple tape turing machine ANSWER IS B DPDA cannot handle languages or grammars with ambiguity, but […]
1 Let R1 and R2 be regular sets defined over alphabet ∑ then (a.) R1 UNION R2 is regular (b.) R1 INTERSECTION R2 is regular (c.) ∑ INTERSECTION R2 IS NOT REGULAR (d.) R2* IS NOT REGULAR 2 Consider the production of the grammar S->AA A->aa A->bb Describe the language […]
(51) S -> a α b I b a c I ab S -> α S I b S -> α bb I ab S -> bdb I b The grammar described above is (A) Context free (B) Context sensitive (C) Regular (D) LR(k) ANSWER: Context sensitive (52) Match […]
(41) The set which is not countable if we have ∑ = {a, b}, is (A) Set of all languages over ∑ accepted by turing machine (B) Set of all regular languages over ∑ (C) Set of all strings over ∑ (D) Set of all languages over ∑ ANSWER: […]
(21) State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = […]
(11) Which one of the following statement is true? (A) The intersection of two context free languages is context free (B) A context free language can always be accepted by a deterministic push down automaton (C) The union of two context free languages is context free (D) The complement of […]