MCQ IN COMPUTER SCIENCE & ENGINEERING

Previous
Next

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Match the following:(i) Regular Grammar (a) Pushdown automaton(ii) Context free Grammar (b) Linear bounded automaton(iii) Unrestricted Grammar (c) Deterministic finite automaton(iv) Context Sensitive Grammar (d) Turing machine(i) (ii) (iii) (iv)
A
(a) (d) (b)
B
(b) (a) (d)
C
(b) (d) (a)
D
(a) (b) (d)
Explanation: 

Detailed explanation-1: -Explanation: Regular grammar is subset of context free grammar.

Detailed explanation-2: -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-3: -A context-free grammar is a set of recursive rules used to generate patterns of strings. A context-free grammar can describe all regular languages and more, but they cannot describe all possible languages. Context-free grammars are studied in fields of theoretical computer science, compiler design, and linguistics.

Detailed explanation-4: -Type 3 Grammar is known as Regular Grammar. Regular languages are those languages which can be described using regular expressions. These languages can be modeled by NFA or DFA. Type 3 is most restricted form of grammar.

There is 1 question to complete.
Previous
Next