Bihar STET – TOC Practice Test | Set 1 ⋆ CSE Study247

Bihar STET – TOC Practice Test | Set 1

Questions 36-40 of 100

0% completed (0/100 answered)

Question 36

MCQ · Single Correct 1 mark

Previous Year Question Bihar STET C.S. 12.09.2023 (Shift-I) PYQ

Which decision algorithm determines whether a given input string w belongs to the language generated by a CFG in CNF (Membership Problem)?

A Pumping Lemma B Determinization C CYK Algorithm (Cocke-Younger-Kasami) D Kleene Star

Question 37

MCQ · Single Correct 1 mark

Is the Emptiness Problem ('Is L(G) = ∅ for a given CFG G?') Decidable?

A Decidable for regular grammars only B Yes, it is Decidable (by checking if the start symbol S can derive any string of terminals) C Decidable for CNF only D No, it is Undecidable

Question 38

MCQ · Single Correct 1 mark

Is the Equivalence Problem ('Do two CFGs G1 and G2 generate the exact same language L(G1) = L(G2)?') Decidable?

A Decidable for DPDA B Yes, it is Decidable C No, it is UNDECIDABLE for general Context-Free Grammars D Decidable in O($n^2)$

Question 39

MCQ · Single Correct 1 mark

What is the Pumping Lemma for Context-Free Languages used for?

A Proving a language is Context-Free B Converting CFG to CNF C Building a PDA D Proving that a specific language is NOT Context-Free (e.g. L = {$a^n$ $b^n$ $c^n$ | n $\ge 1}$)

Question 40

MCQ · Single Correct 1 mark

Previous Year Question Bihar STET C.S. 12.06.2024 (Shift-II) PYQ

What class of languages is generated by Right-Linear (or Left-Linear) Grammars?

A Regular Languages B Context-Free Languages C Context-Sensitive Languages D Recursively Enumerable