Test: DPDA & Ambiguous Grammars - Computer Science Engineering (CSE) MCQ

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.

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

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.

None.

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.