COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Match the following:List-I List-IIa. Context free grammar i. Linear bounded automatonb. Regular grammar ii. Pushdown automatonc. Context sensitive grammar iii. Turing machined. Unrestricted grammar iv. Deterministic finite automatoncode:a b c d
|
|
ii iv iii i
|
|
|
ii iv i iii
|
|
|
iv i ii iii
|
|
|
i iv iii ii
|
Explanation:
Detailed explanation-1: -Context free grammar is a formal grammar which is used to generate all possible strings in a given formal language. Context free grammar G can be defined by four tuples as: G= (V, T, P, S)
Detailed explanation-2: -CFG and PDA are equivalent in power: a CFG generates a context-free language and a PDA recognizes a context-free language.
Detailed explanation-3: -In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions. A linear language is a language generated by some linear grammar.
There is 1 question to complete.