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

CFGs are more powerful than:(a) DFA(b) NDFA(c) Mealy Machine(d) All of

1.	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.

Discussion

No Comment Found

Related InterviewSolutions

Which of the following are context free language?(a) L={a^ib^i|i>=0}(b) L={ww^r| w is a string and r represents reverse}(c) Both (a) and (b)(d) one of the mentionedThe question was posed to me by my school teacher while I was bunking the class.My enquiry is from DPDA and Ambiguous Grammars topic in chapter Push Down Automata of Automata Theory
|-* is the __________ closure of |-(a) symmetric and reflexive(b) transitive and reflexive(c) symmetric and transitive(d) none of the mentionedThe question was asked in an online interview.My doubt stems from Deterministic PDA in portion Push Down Automata of Automata Theory
Which among the following is not a part of the Context free grammar tuple?(a) End symbol(b) Start symbol(c) Variable(d) ProductionThis question was posed to me in semester exam.Question is taken from PDA-acceptance by Empty Stack topic in division Push Down Automata of Automata Theory
Halting states are of two types. They are:(a) Accept and Reject(b) Reject and Allow(c) Start and Reject(d) None of the mentionedThis question was posed to me during an interview.I need to ask this question from From Grammars to Push Down Automata topic in chapter Push Down Automata of Automata Theory
A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.(a) 5(b) 8(c) 4(d) 10I have been asked this question in an interview.The origin of the question is PDA-Acceptance by Final State in chapter Push Down Automata of Automata Theory
State true or false:Statement: The operations of PDA never work on elements, other than the top.(a) Statement: The operations of PDA never work on elements, other than the top.(b) true(c) falseThe question was asked during an internship interview.My question is based upon PDA-Acceptance by Final State topic in division Push Down Automata of Automata Theory
Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.(a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*(b) (bbbb+aaaa)*(c) ((a+b)(a+b)(a+b)(a+b))*(d) None of the mentionedThis question was posed to me in a national level competition.Query is from Regular Languages and D-PDA topic in section Push Down Automata of Automata Theory
Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.(a) 120(b) 625(c) 360(d) 36This question was addressed to me in an international level competition.My question is taken from Regular Languages and D-PDA in division Push Down Automata of Automata Theory
Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?(a) Moves(b) transition function(c) or/not symbol(d) none of the mentionedThe question was asked in my homework.My query is from From Grammars to Push Down Automata topic in chapter Push Down Automata of Automata Theory
If P is the production, for the given statement, state true or false.(a) * represents that the left hand side production rule has no right or left context.(b) true(c) falseI had been asked this question in an interview.My doubt stems from DPDA and Context Free Languages in portion Push Down Automata of Automata Theory

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

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment