Test: DPDA & Ambiguous Grammars


10 Questions MCQ Test Theory of Computation | Test: DPDA & Ambiguous Grammars


Description
This mock test of Test: DPDA & Ambiguous Grammars for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: DPDA & Ambiguous Grammars (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: DPDA & Ambiguous Grammars quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: DPDA & Ambiguous Grammars exercise for a better result in the exam. You can find other Test: DPDA & Ambiguous Grammars extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

CFGs are more powerful than:

Solution:

Context-free grammars are strictly more powerful than regular expressions:
1) Any language that can be generated using regular expressions can be generated by a context-free grammar.
2) There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.
As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.

QUESTION: 2

State true or false:S-> 0S1|01Statement: No regular expression exists for the given grammar.

Solution:

 The grammar generates a language L such that L={0n1n|n>=1} which is not regular. Thus, no regular expression exists for the same.

QUESTION: 3

 For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error.
(1) -> 
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Solution:

–> 
–> | epsilon
–> ‘.’ | epsilon
–> ‘E’ | epsilon
–> + | – | epsilon
–> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

QUESTION: 4

Which among the following is incorrect with reference to a derivation tree?

Solution:

The root or interms of the grammar, starting variable can not be a terminal.

QUESTION: 5

Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?

Solution:

he step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa

QUESTION: 6

Statement 1: Ambiguity is the property of grammar but not the language.
Statement 2: Same language can have more than one grammar.
Which of the following options are correct with respect to the given statements?

Solution:

One language can more than one grammar. Some can be ambiguous and some cannot.

QUESTION: 7

Which of the following are non essential while simplifying a grammar?

Solution:

Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.

QUESTION: 8

Which of the following are context free language?

Solution:

None.

QUESTION: 9

The language L ={ai2bi|i>=0} is:

Solution:

The language is recursive and every recursive language is a CFL.

QUESTION: 10

 L->rLt|tLr|t|r
The given grammar produces a language which is:

Solution:

As there exists no production for the palindrome set, even palindromes like abba, aabbaa, baaaaaab, etc will not be generated.

Related tests