COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
Only context free grammar
|
|
Only context sensitive grammar
|
|
Only regular grammar
|
|
Context free grammar or regular grammar
|
Detailed explanation-1: -All the languages that are accepted by finite automata are known as regular language. Grammar that generates regular languages is regular grammar. So, a push down automata accepts both regular and context free languages.
Detailed explanation-2: -Since pushdown automata recognize context-free languages, and context-free languages include regular languages, pushdown automata accept regular languages. A pushdown automaton is just a finite state machine augmented with a stack.
Detailed explanation-3: -The main relationship between context free grammars and pushdown automata is that both models define the same languages. In other words, every con-text free language is accepted by some pushdown automaton, and every push-down automaton accepts a context free language.
Detailed explanation-4: -Pushdown automata are equivalent in power to context-free grammars. A stack is valuable because it can hold an unlimited amount of information. Consider the language • Finite automaton is unable to recognize this language.
Detailed explanation-5: -2) If a language is recognized by a push-down automaton, then it is a context-free language. The basic idea of the proof is to construct a context-free grammar G from a push-down automaton M, satisfying L(G) = L(M).