MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -Every context-free grammar is context-sensitive grammar and context-sensitive grammar is accepted by Linear Bounded Automata. So, context-free grammar is also accepted by Linear Bounded Automata. Hence the correct answer is both two-way linear bounded and Push down automata.

Detailed explanation-2: -For any linear-bounded grammar G there exists a linear-bounded automaton which accepts the language L(G) generated by G. It follows immediately from these lemmas that for any context-sensi-tive language there exists a linear-bounded automaton which generates it.

Detailed explanation-3: -L can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts L. The language can easily be shown to be neither regular nor context free by applying the respective pumping lemmas for each of the language classes to L.

Detailed explanation-4: -8.1 INTRODUCTION. A linear bounded automaton (lba) is a nondeterministic single-tape Turing. machine which never leaves those cells on which the input was placed. Formally, a linear bounded automaton is denoted by M = (K, E, F, 3, q0, F).

Detailed explanation-5: -A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length. Length = function (Length of the initial input string, constant c) Here, Memory information ≤ c × Input information. The computation is restricted to the constant bounded area.