GATE CSE Context-Free Languages, Grammars & Pushdown Automata – TOC Practice Test

GATE CSE Context-Free Languages, Grammars & Pushdown Automata – TOC Practice Test | Set 1

Questions 61-65 of 100

0% completed (0/100 answered)

Question 61

MCQ · Single Correct 1 mark

Which construction shows CFL ∩ regular is CFL?

A Product of a PDA with a DFA B Conversion to a two-stack PDA C Complementing the PDA D Product of two CFGs

MCQ · Single Correct 1 mark

Which normal form is particularly useful for top-down parsing because each production begins with a terminal?

A Regular form B Chomsky hierarchy C CNF D GNF

MCQ · Single Correct 1 mark

Which grammar is in GNF?

A S -> Aa, A -> b B $S -> aS | \epsilon$ C S -> aAB, A -> b, B -> c D S -> AB, A -> a

NAT · Numerical Answer 1 mark

For a CNF parse tree deriving a nonempty string of length 50, how many total production applications occur?

Enter your numerical answer

MCQ · Single Correct 1 mark

Which statement about DPDA language class is true?

A DCFL is a strict subset of CFL B DCFL equals CFL C DCFL is disjoint from regular languages D DCFL contains all context-sensitive languages