1. The technique of automation with a stack as an auxiliary storage is called as Pushdown Automata 2. Context Free Grammar(CFG) is A language generator 3. A graph is a collection of Vertices and edges 4. A graph with no edges is called as Empty graph or Trivial graph […]
1) Let A and B be any two arbitrary events then which one of the following is true ? P( A intersection B) = P(A). P(B) P(A union B) = P(A) + P(B) P(AB) = P(A intersection B). P(B) P(A union B) >= P(A) + P(B) Answer = D […]
Which of the following is tautology? a.)x v y b.)x v (~y) c.)x v(~x) d.)(x=<y)^(x<=y) Ans.: c.) Explanation: X ~X X V(~X) T F T F T T Tip: ‘~’ denotes negation that is ‘1’ means ‘0’ and ‘0’ means ‘1’ ‘V’ means ‘OR’ […]
DISCRETE STRUCTURE MCQ SET 1 DISCRETE STRUCTURE MCQ SET 2 DISCRETE STRUCTURE MCQ SET 3 DISCRETE STRUCTURE MCQ SET 4 DISCRETE STRUCTURE MCQ SET 5 DISCRETE STRUCTURE MCQ SET 6
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 […]