Context Free Grammar MCQ

Test your knowledge with important Context Free Grammar MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Context Free Grammar MCQs at Bissoy

• Which of these does not belong to CFG?
  ক

  Terminal Symbol

  খ

  Non terminal Symbol

  গ

  Start symbol

  ঘ

  End Symbol
• A CFG is closed under _________
  ক

  Union

  খ

  Kleene star

  গ

  Concatenation

  ঘ

  None of the mentioned
• A regular Grammar is a _________
  ক

  CFG

  খ

  Non CFG

  গ

  English Grammar

  ঘ

  None of the mentioned
• Push down automata accepts which language?
  ক

  Context sensitive language

  খ

  Context free language

  গ

  Recursive language

  ঘ

  None of the mentioned
• The context free grammar S → SS | 0S1 | 1S0 | ɛ generates _________
  ক

  Equal number of 0’s and 1’s

  খ

  Unequal number of 0’s and 1’s

  গ

  Number of 0’s followed by any number of 1’s

  ঘ

  None of the mentioned
• The context free grammar S → A111|S1, A → A0 | 00 is equivalent to _________
  ক

  {0n1m | n=2, m=3}

  খ

  {0n1m | n=1, m=5}

  গ

  {0n1m | n should be greater than two and m should be greater than four}

  ঘ

  None of the mentioned
• A context free language is called ambiguous if _________
  ক

  It has 2 or more left derivations for some terminal string ѡ є L (G)

  খ

  It has 2 or more right derivations for some terminal string ѡ є L (G)

  গ

  It has 2 or more left & right derivations for some terminal string ѡ є L (G)

  ঘ

  None of the mentioned
• Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?
  ক

  S1 is correct and S2 is not correct

  খ

  Both S1 and S2 are correct

  গ

  Both S1 and S2 are not correct

  ঘ

  S1 is not correct and S2 is correct
• Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?
  ক

  I only

  খ

  II only

  গ

  Both I and II

  ঘ

  Neither I nor II
• Which of the following language accepted by a Push down Automata?
  ক

  Type0

  খ

  Type1

  গ

  Type2

  ঘ

  Type3
• Grammars that can be translated to DFAs is ___________
  ক

  Left linear grammar

  খ

  Right linear grammar

  গ

  Generic grammar

  ঘ

  All of the mentioned
• Automaton accepting the regular expression of any number of a’ s is ___________
  ক

  a*

  খ

  ab*

  গ

  (a/b)*

  ঘ

  a*b*c
• Grammar that produce more than one Parse tree for same sentence is ___________
  ক

  Ambiguous

  খ

  Unambiguous

  গ

  Complementation

  ঘ

  Concatenation Intersection
• Recursively enumerable languages are not closed under ______________
  ক

  Union

  খ

  Intersection

  গ

  Complementation

  ঘ

  Concatenation
• Consider the grammar given below E? E+E | E*E | E-E | E/E | E^E | (E) | id Assume that + and ^ have the same but least precedence, * and / have the next higher precedence but the same precedence and finally ^ has the highest precedence. Assume + and ^ associate to the left like * and / and that ^ associates to the right. Choose the correct for the ordered pairs (^,^), (-,-), (+,+), (*,*) in the operator precedence table constructed for the grammar.
  ক

  All <

  খ

  All >

  গ

  < >, =

  ঘ

  < > > >
• Which of the following conversion is not possible (algorithmically)?
  ক

  Regular grammar to CFG

  খ

  NDFA to DFA

  গ

  NDPDA to DPDA

  ঘ

  NDTM to DTM
• If P & R are regular and also given that if PQ=R, then?
  ক

  Q has to be regular

  খ

  Q cannot be regular

  গ

  Q need not be regular

  ঘ

  Q has to be a CFL
• Assume the statements S1 and S2 given as: S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite. S2: There exists an algorithm to determine whether two context free grammars generate the same language. Which of the following is true?
  ক

  S1 is correct and S2 is not correct

  খ

  Both S1 and S2 are correct

  গ

  Both S1 and S2 are not correct

  ঘ

  S1 is not correct and S2 is correct