Context-Free Grammars and Ambiguity Essentials Quiz Quiz

Enhance your understanding of context-free grammars, their properties, and ambiguity in formal languages with this targeted quiz. Designed to introduce key terms, concepts, and practical examples, this quiz helps learners grasp the role of context-free grammars and the meaning of ambiguity in syntax analysis.

1. Defining Context-Free Grammar

   Which best defines a context-free grammar (CFG) in formal language theory?

   1. A grammar where the left-hand side of every production consists of a single non-terminal symbol
   2. A grammar that generates only finite languages
   3. A grammar where productions must have only one symbol on both sides
   4. A grammar where each production maps a terminal to a non-terminal

   Explanation: A context-free grammar is defined such that each production replaces a single non-terminal with a string of terminals and/or non-terminals. The other options are incorrect because context-free grammars can have more than one symbol on the right-hand side, do not require mapping only terminals to non-terminals, and can generate infinite as well as finite languages.

2. Ambiguous Grammar Detection

   If a grammar allows at least one string to have two distinct parse trees, what is this property called?

   1. Determinism
   2. Recursion
   3. Ambiguity
   4. Associativity

   Explanation: Ambiguity in a grammar occurs when a string can be generated in more than one way, resulting in different parse trees. Recursion relates to productions referring to themselves. Associativity deals with how operators group, and determinism involves choices without conflicts.

3. Example of Non-Ambiguous Grammar

   Which of the following grammars is guaranteed to be non-ambiguous?

   1. A grammar that includes epsilon (empty string) productions
   2. A grammar with multiple non-terminal start symbols
   3. A grammar with left-recursive rules
   4. A grammar producing only a single string

   Explanation: If a grammar generates only one string, there cannot be more than one parse tree for it, so it must be non-ambiguous. Having left-recursion, multiple start symbols, or epsilon productions does not automatically guarantee non-ambiguity, as these can still lead to multiple parse trees for the same string.

4. Recognizing an Ambiguous Grammar

   Given the grammar S → S + S | S * S | a, why might this grammar be ambiguous for the string 'a + a * a'?

   1. Because the grammar cannot produce the string 'a + a * a'
   2. Because the grammar generates only terminal symbols
   3. Because the grammar is regular, not context-free
   4. Because 'a + a * a' has more than one valid parse tree in this grammar

   Explanation: For the string 'a + a * a', the grammar allows multiple parse trees due to lack of operator precedence, which is a classic case of ambiguity. The other options are incorrect: the grammar is context-free, it can generate the string, and it has non-terminals as well as terminals.

5. Eliminating Ambiguity

   What is a common method for removing ambiguity from arithmetic grammars?

   1. Adding more start symbols to the grammar
   2. Refining the grammar with explicit precedence and associativity rules
   3. Replacing all terminals with non-terminals
   4. Allowing productions for every possible string

   Explanation: Ambiguity is frequently resolved by structuring the grammar to enforce operator precedence and associativity (e.g., separate rules for addition and multiplication). Allowing every possible string, changing all terminals, or introducing more start symbols do not address ambiguity and can even make the grammar more confusing.

6. Epsilon Productions and Ambiguity

   Can the presence of epsilon (empty string) productions in a grammar directly cause ambiguity?

   1. Not necessarily, but they can contribute to ambiguity in some cases
   2. Epsilon productions are not allowed in context-free grammars
   3. No, epsilon productions always make grammars non-ambiguous
   4. Yes, every epsilon production introduces ambiguity

   Explanation: Epsilon productions do not inherently make a grammar ambiguous, but in some cases, when combined with other rules, they can create multiple parse trees for the same string. It is incorrect to say they always or never introduce ambiguity, and context-free grammars do allow epsilon productions.

7. Language Generated by CFG

   Which type of language is always generated by some context-free grammar?

   1. Recursive languages only
   2. Regular languages only
   3. Unrestricted languages
   4. Context-free languages

   Explanation: Every context-free language is by definition generated by a context-free grammar. Regular and recursive languages are classes that may or may not be context-free, and unrestricted languages encompass types that go beyond what context-free grammars can produce.

8. Parsing and Ambiguity

   What is a consequence of using an ambiguous context-free grammar in syntax analysis?

   1. A string may have more than one parse tree, leading to confusion in interpretation
   2. Ambiguous grammars always produce infinite languages
   3. Parsing algorithms work faster on ambiguous grammars
   4. All strings are generated only once

   Explanation: The situation where a string can be derived in multiple ways means the structure is unclear, potentially leading to ambiguity in how the string should be interpreted. The other options are incorrect because ambiguous grammars do not guarantee unique derivations, do not necessarily improve speed, nor always correspond to infinite languages.

9. Productions in a CFG

   In a context-free grammar, a production like A → aBa means which of the following?

   1. Only 'a' can be generated by A
   2. The non-terminal a can be replaced with 'Aba'
   3. The non-terminal B must always appear between two terminal symbols
   4. The non-terminal A can be replaced with the string 'aBa'

   Explanation: The production A → aBa means that whenever A is encountered during derivation, it can be replaced by 'aBa'. The other options are either misleading or too restrictive. 'a' is not a non-terminal, B is not required everywhere, and A can generate more than just 'a'.

10. Checking for Ambiguity

    Which method is commonly used to check if a context-free grammar is ambiguous?

    1. Find a string with more than one distinct parse tree
    2. Check if left recursion exists in the grammar
    3. Count the number of productions in the grammar
    4. List all terminal symbols generated by the grammar

    Explanation: To show ambiguity, one typically needs to exhibit a string having more than one parse tree. Listing terminals, counting productions, or looking for left recursion does not directly assess ambiguity, although these aspects may relate to other properties of the grammar.