CFL- Other Normal Forms MCQ

Test your knowledge with important CFL- Other Normal Forms MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30+ more CFL- Other Normal Forms MCQs on Bissoy. Bissoy App

• Which among the following is a correct option in format for representing symbol and expression in Backus normal form?
  ক

  <symbol> ->expression

  খ

  <symbol>::=_expression_

  গ

  <symbol>=<expression>

  ঘ

  all of the mentioned
• Which of the following is true for Valiants algorithm?
  ক

  an extension of CYK

  খ

  deals with efficient multiplication algorithms

  গ

  matrices with 0-1 entries

  ঘ

  all of the mentioned
• The __________ running time of CYK is O(n3 .|G|) where n is the length of the parse string and |G| is the size of the context free grammar G.
  ক

  worst

  খ

  best

  গ

  average

  ঘ

  none of the mentioned
• The standard version of CYK algorithm operates only on context free grammars in the following form:
  ক

  Greibach Normal form

  খ

  Chomsky Normal form

  গ

  Backus Naur form

  ঘ

  All of the mentioned
• Which among the following can parse a context free grammar?
  ক

  top down parser

  খ

  bottom up parser

  গ

  CYK algorithm

  ঘ

  all of the mentioned
• Which of the following grammars is similar to Floyd Normal form?
  ক

  Backus Naur Form

  খ

  Kuroda Normal Form

  গ

  Greibach Normal Form

  ঘ

  Chomsky Normal Form
• Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.
  ক

  top-down parser

  খ

  bottom-up parser

  গ

  multitape turing machine

  ঘ

  none of the mentioned
• Which of the following can generate Unrestricted grammars?
  ক

  Pentonnen Normal form

  খ

  Floyd Normal form

  গ

  Greibach Normal form

  ঘ

  None of the mentioned
• Every Kuroda Normal form grammar generates ___________
  ক

  Context free grammar

  খ

  Context sensitive grammar

  গ

  Unrestricted grammar

  ঘ

  None of the mentioned
• The following format of grammatical notation is accepted by which of the following: AB->CD A->BC or A->B or A->a where A, B, C, D are non terminal symbols and a is a terminal symbol.
  ক

  Greibach Normal Form

  খ

  Chomsky Nrmal Form

  গ

  Kuroda Normal Form

  ঘ

  None of the mentioned