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: […]