Back to the 2022 paper
Similar questions
Formal Language & Automata TheoryA _____ is context free grammar with atmost one non-terminal in the right handside of the production. (i) linear grammar (ii) linear bounded grammar (iii) regular grammar (iv) None of the above20202mFormal Language & Automata TheoryContext-Free Grammars are equivalent to (i) Finite Automata (ii) Turing Machines (iii) Linear Bounded Automata (iv) Pushdown Automata20252mFORMAL LANGUAGE & AUTOMATA THEORYWhich of the following is a type of grammar in the Chomsky hierarchy? (i) Regular (ii) Context-Free (iii) Context-Sensitive (iv) All of the above20242m Compiler DesignChoose the correct option / answer the following: Which grammar type is recognized by a push-down automaton? (i) Regular (ii) Context-free (iii) Context-sensitive (iv) Unrestricted20242m
PreviousDefinition of a language L with alphabet \{a\} is given as L= \{a^{nk} / k > 0, \text{ and } n \text{ is a positive integer constant}\}. What is the minimum number of states needed in a DFA to recognize L? (i) k + 1 (ii) n + 1 (iii) 2n + 1 (iv) 2k + 1NextLet N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n