Context-Free Grammars (CFGs)

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Which component is NOT part of the definition of a Context-Free Grammar (CFG)?

A finite set of productions.
A designated start symbol.
An alphabet of terminals.
A set of semantic rules. (correct)

Consider a CFG with the production rule `A -> aA | b`. Which of the following strings CANNOT be derived from the non-terminal `A`?

b
ab
aaab
aba (correct)

In the context of formal grammars, what is the primary difference between a terminal and a non-terminal symbol?

Terminals can be further replaced by other symbols, while non-terminals cannot.
Non-terminals can be further replaced by other symbols, while terminals cannot. (correct)
Terminals are always uppercase, while non-terminals are always lowercase.
Non-terminals are part of the input string, while terminals are part of the grammar rules.

Which of the following best describes the process of 'parsing' a sentence with respect to a given grammar?

Determining how the sentence can be formed from the rules of the grammar. (A) Signup and view all the answers

Given the grammar with the following productions: `S -> AB` `A -> aA | a` `B -> bB | b` Which of the following strings can be generated by this grammar?

aabb (A) Signup and view all the answers

Consider a grammar with the production rules: `S -> aSb | ε` (where ε represents the empty string). What language does this grammar generate?

All strings of the form a^n b^n, where n >= 0. (D) Signup and view all the answers

What is the significance of the 'start symbol' in a Context-Free Grammar (CFG)?

It's a non-terminal from which all strings in the language are derived. (A) Signup and view all the answers

Which of the following best defines a 'derivation' in the context of Context-Free Grammars?

The sequence of applying grammar rules to produce a string of terminals from the start symbol. (A) Signup and view all the answers

In a grammar designed to reflect operator precedence, which of the following is true about the placement of productions for addition and subtraction (+, -) relative to multiplication and division (*, /)?

Productions for (+, -) should appear before productions for (*, /) to denote lower precedence. (D) Signup and view all the answers

When constructing a syntax tree, which of the following principles dictates the vertical positioning of operator productions?

Operators evaluated earlier are placed lower in the tree, further from the root. (A) Signup and view all the answers

Consider the following context-free grammar (CFG): `S -> aS | Sa | a`. Why is this grammar considered ambiguous?

Because there exists at least one string that can be derived using two distinct syntax trees. (C) Signup and view all the answers

In the context of syntax trees, what do the leaves of the tree represent?

Terminals of the CFG. (A) Signup and view all the answers

What is the primary criterion for a context-free grammar (CFG) to be classified as ambiguous?

It allows for multiple leftmost derivations for at least one string. (B) Signup and view all the answers

What characteristic of a context-free grammar leads to different syntax trees for the same string?

Allowing different orders of applying production rules to derive the same string. (A) Signup and view all the answers

Consider the expression `5 + 3 * 2`. According to operator precedence, which syntax tree structure is correct?

A tree where <code>+</code> is the root, and <code>*</code> is a child, indicating <code>5 + (3 * 2)</code>. (A) Signup and view all the answers

Given a CFG for arithmetic expressions, how does the syntax tree visually represent the order of operations?

Nodes closer to the root are evaluated later, while nodes further from the root are evaluated earlier. (C) Signup and view all the answers

Which of the following is a direct consequence of a context-free grammar being ambiguous?

A compiler might interpret a program in multiple, conflicting ways. (D) Signup and view all the answers

Consider the following CFG: `S -> S + S | id`. Identify a primary issue that arises when using this grammar for parsing expressions like `id + id + id`.

The grammar is ambiguous, leading to multiple possible parse trees and evaluation orders. (C) Signup and view all the answers

Consider a context-free grammar (CFG) with the production rules: `S -> aS | ^`. Which language does this CFG generate?

The language consisting of any number of 'a's, including the empty string. (B) Signup and view all the answers

Which of the following context-free grammars (CFGs) generates the language (a+b)*?

<code>S -> aS | bS | ^</code> (B) Signup and view all the answers

Given the context-free grammar (CFG): `S -> X | Y`, `X -> aX | bX | a | b`, `Y -> ^`. Which language does this CFG generate?

The language of all strings containing only 'a's and 'b's, including the null string. (C) Signup and view all the answers

Which of the following context-free grammars (CFGs) generates the language of odd palindromes over the alphabet {a, b}?

<code>S -> aSa | bSb | a | b</code> (C) Signup and view all the answers

Which context-free grammar (CFG) generates the language of even palindromes over the alphabet {a, b}?

<code>S -> aSa | bSb | ^</code> (C) Signup and view all the answers

Which of the following context-free grammars (CFGs) generates the language where the number of 'a's is equal to the number of 'b's?

Given the context-free grammar (CFG): `S -> XaaX`, `X -> aX | bX | ^`. Which language does this CFG generate?

Strings that consist of any combination of 'a's and 'b's with 'aa' in the middle. (C) Signup and view all the answers

Consider the following CFG: `S -> XY`, `X -> aX | bX | a`, `Y -> Ya | Yb | a`. What kind of strings does S generate?

Strings composed of 'a's and 'b's, beginning with 'a' and ending with 'a'. (C) Signup and view all the answers

Given the CFG: `S -> XbaaX | aX`, `X -> aX | bX | ^`. Which language is generated by this grammar?

Strings containing 'baa' as a substring. (C) Signup and view all the answers

What language does the following context-free grammar (CFG) generate? `S -> aSa | b`

Strings where 'b' is surrounded by the same number of 'a's on both sides. (C) Signup and view all the answers

Consider the context-free grammar (CFG): `S -> aSb | ^`. Which language does it generate?

Strings where the number of 'a's and 'b's are equal, with all 'a's preceding all 'b's , including the null string. (B) Signup and view all the answers

Which of the following describes the purpose of left recursion in a context-free grammar?

To ensure operators of the same precedence are evaluated from left to right. (C) Signup and view all the answers

Which rule is used while creating CFGs for expressions with operators like '+', '-', '*' and '/'?

Left recursive grammar for left associative operators. (A) Signup and view all the answers

Consider the language where variable names in a programming language must start with a letter or underscore, followed by any combination of letters, digits, or underscores. Which of the following CFG productions captures this rule?

<code>Identifier -> X Y</code>, <code>X -> Letter | Underscore</code>, <code>Y -> Letter Y | Digit Y | _ Y | ^</code> (A) Signup and view all the answers

In the context of formal languages, what is the significance of the symbol '^' in a context-free grammar (CFG)?

It represents the null or empty string. (C) Signup and view all the answers

Flashcards

Context Free Grammar (CFG)

A CFG consists of an alphabet of terminals, non-terminal symbols, and production rules.

Terminals

Words that cannot be replaced within the grammar are called terminals.

Non-Terminals

Symbols in the grammar that can be replaced by other symbols or terminals.

Production

Rules that define how non-terminals can be replaced or expanded into terminals or other non-terminals.