LEXICAL ANALYSIS
CONSTRUCTION OF A LEXICAL ANALYZER
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Turing Machine
|
|
|
Linear Bounded Automata
|
|
|
Push Down Automata
|
|
|
Finite Automata
|
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: -Explanation: Context sensitive languages are recognized with the help of linear bounded automata.
Detailed explanation-3: -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-4: -An equivalent definition of an LBA is that it uses only constant (c) times the amount of space occupied by the input string, where c is a constant fixed for the particular machine. Q is a finite non empty set of states. A is the finite non empty set of input alphabet. is the finite tape alphabet which contains A.