InterviewSolution

Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

51.	Which of the following is the correct representation of grammar for the given regular expression? a(aUb)*b(a) (1) S → aMb (2) M → e (3) M → aM (4) M → bM(b) (1) S → aMb (2) M → Mab (3) M → aM (4) M → bM(c) (1) S → aMb (2) M → e (3) M → aMb (4) M → bMa(d) None of the mentionedI had been asked this question in final exam.My question is based upon DPDA and Context Free Languages in chapter Push Down Automata of Automata Theory
Answer» Correct option is (a) (1) S → aMb (2) M → e (3) M → aM (4) M → bM Easy explanation: The basic idea of grammar FORMALISMS is to CAPTURE the structure of STRING by a) using special symbols to stand for substrings of a particular structure b) using rules to SPECIFY how the substrings are COMBINED to form new substrings.

52.	The context free grammar which generates a Regular Language is termed as:(a) Context Regular Grammar(b) Regular Grammar(c) Context Sensitive Grammar(d) None of the mentionedThe question was asked in an online interview.This key question is from PDA-acceptance by Empty Stack in section Push Down Automata of Automata Theory
Answer» Right answer is (b) Regular Grammar Explanation: Regular grammar is a subset of Context FREE grammar. The CFGS which produces a language for which a FINITE AUTOMATON can be created is called Regular grammar.

53.	CFGs are more powerful than:(a) DFA(b) NDFA(c) Mealy Machine(d) All of the mentionedThe question was asked in a job interview.The doubt is from DPDA and Ambiguous Grammars in section Push Down Automata of Automata Theory
Answer» The correct CHOICE is (d) All of the mentioned For explanation I would say: Context-free grammars are strictly more powerful than regular EXPRESSIONS: 1) Any LANGUAGE that can be generated USING regular expressions can be generated by a context-free grammar. 2) There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression. As a corollary, CFGs are strictly more powerful than DFAS and NDFAs.

54.	The transition a Push down automaton makes is additionally dependent upon the:(a) stack(b) input tape(c) terminals(d) none of the mentionedThe question was posed to me by my college professor while I was bunking the class.This key question is from Deterministic PDA topic in chapter Push Down Automata of Automata Theory
Answer» The CORRECT choice is (a) stack Easy explanation: A PDA is a finite MACHINE which has an additional stack storage. Its TRANSITIONS are based not only on INPUT and the correct state but ALSO on the stack.

55.	Which of the following correctly resembles the given state diagram?(a) {ww^r\|w=(a+b)*}(b) ε is called the initial stack symbol(c) Both (a) and (b)(d) None of the mentionedI have been asked this question at a job interview.Origin of the question is From PDA to Grammars in chapter Push Down Automata of Automata Theory
Answer» Right option is (a) {ww^r\|W=(a+b)*} For explanation: Initially we put a special symbol ‘#’ into the empty stack. At STATE q1, the w is being read. In state q2, each 0 or 1 is popped when it MATCHES the input. If any other input is given, the PDA will go to a DEAD state. When we REACH that special symbol ‘#’, we go to the accepting state q3.

56.	The moves in the PDA is technically termed as:(a) Turnstile(b) Shifter(c) Router(d) None of the mentionedThe question was asked at a job interview.My question is based upon From PDA to Grammars topic in portion Push Down Automata of Automata Theory
Answer» Right choice is (a) TURNSTILE For EXPLANATION: A turnstile notation is USED for connecting PAIRS OD ID’s taht represents one or many moves of a PDA.

57.	Which of the following is analogous to the following?:NFA and NPDA(a) Regular language and Context Free language(b) Regular language and Context Sensitive language(c) Context free language and Context Sensitive language(d) None of the mentionedI had been asked this question by my college professor while I was bunking the class.The query is from Regular Languages and D-PDA topic in division Push Down Automata of Automata Theory
Answer» The correct answer is (a) REGULAR LANGUAGE and Context Free language To explain: All regular LANGUAGES can be accepted by a non DETERMINISTIC finite automata and all context free languages can be accepted by a non deterministic PUSH down automata.

58.	Which of the following statement is false?(a) For non deterministic PDA, equivalence is undecidable(b) For deterministic PDA, equivalence is decidable(c) For deterministic PDA, equivalence is undecidable.(d) None of the mentionedThe question was posed to me in an online interview.This intriguing question comes from From PDA to Grammars in section Push Down Automata of Automata Theory
Answer» Right answer is (c) For deterministic PDA, EQUIVALENCE is undecidable. Easiest explanation: Geraud PROVED the equivalence problem DECIDABLE for Deterministic PDA .

59.	For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form of __________(a) A(b) A^nZ0, n>=0(c) Z0A^n, n>=0(d) None of the mentionedI got this question in examination.This interesting question is from From Grammars to Push Down Automata topic in portion Push Down Automata of Automata Theory
Answer» The correct option is (B) A^nZ0, N>=0 Best explanation: The possible change in the STACK contents is a change in the number of A’s on the stack.

60.	A string is accepted by a PDA when(a) Stack is empty(b) Acceptance state(c) Both (a) and (b)(d) None of the mentionedThis question was addressed to me in an internship interview.I want to ask this question from PDA-Acceptance by Final State in section Push Down Automata of Automata Theory
Answer» Correct choice is (c) Both (a) and (B) Easiest explanation: When we reach the acceptance STATE and find the STACK to be empty, we say, the string has been ACCEPTED by the push down automata.