COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
a) 2-way linear bounded automata
|
|
|
b) push down automata
|
|
|
both a and b
|
|
|
Finite state automata
|
Detailed explanation-1: -Context-free Grammar (CFG) can recognize two-way linear bounded automata and pushdown automata (deterministic pushdown automata and non-deterministic pushdown automata). Every context-free grammar is context-sensitive grammar and context-sensitive grammar is accepted by Linear Bounded Automata.
Detailed explanation-2: -CFG stands for context-free grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as: G = (V, T, P, S)
Detailed explanation-3: -We can prove that a language is context-free if we construct a context-free grammar that generates it. Alternatively, we can create a pushdown automaton that recognizes the language. On the other hand, we use Ogden’s lemma and the pumping lemma for context-free languages to prove that a language isn’t context-free.
Detailed explanation-4: -Context-Free Language (CFL) is a language which is generated by a context-free grammar or Type 2 grammar(according to Chomsky classification) and gets accepted by a Pushdown Automata.
Detailed explanation-5: -All regular languages are context-free languages, but not all context-free languages are regular. Most arithmetic expressions are generated by context-free grammars, and are therefore, context-free languages.