DPDA & Ambiguous Grammars - Free MCQ Practice Test with solutions, GATE

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.

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

Answer: Option A - 3

The production given in line 3 is incorrect because the fractional part of a real number must allow a decimal point followed by digits; the current line has no token for the decimal point.

The minimal correct form for the fractional part is: '.' digits | epsilon, where digits denotes one or more digits defined by line 6.

Line 6 correctly lists the digits. Line 5 correctly provides an optional sign. Line 4 supplies the exponent marker 'E' or epsilon, so the only syntactic error that must be fixed to allow fractional numbers is in line 3.

Therefore the erroneous line is 3.

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

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

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

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.

C is correct. Both languages are context-free.

For L₁, a context-free grammar that generates the language is S → a S b | ε. This grammar produces strings with equal numbers of as followed by bs, so L₁ is context-free.

For L₂, a nondeterministic pushdown automaton (NPDA) recognises the language by nondeterministically guessing the midpoint: it pushes symbols of the first half of the input onto the stack, then switches to popping and matching symbols while reading the second half. This accepts exactly strings of the form ww^r, so L₂ is context-free.

Therefore both languages are context-free and the correct option is C.

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

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