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={0^{n}1^{n}|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.

### Context Free Grammars

Doc | 24 Pages

### Context Free Grammars (CFG)

Doc | 7 Pages

### Formalism Derivations - Context-Free Grammars

Doc | 28 Pages

- Test: DPDA & Ambiguous Grammars
Test | 10 questions | 10 min

- Test: From PDA to Grammars
Test | 10 questions | 10 min

- Test: DPDA & Context Free Languages
Test | 10 questions | 10 min

- Test: Context-Free Grammars & Push-Down Automata
Test | 30 questions | 90 min

- Test: From Grammars to Push Down Automata
Test | 10 questions | 10 min