Test: DPDA And Ambiguous Grammars


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


Description
This mock test of Test: DPDA And 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 And Ambiguous Grammars (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: DPDA And Ambiguous Grammars quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: DPDA And Ambiguous Grammars exercise for a better result in the exam. You can find other Test: DPDA And 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