4.3 Context-free languages

• A Context-Free Grammar (CFG) is a formal language defined by a set of Production Rules
• Match the CFG components with their descriptions:

  Variables ↔️ Symbols that can be replaced using production rules

  Terminals ↔️ Symbols in the final strings generated by the grammar

  Production Rules ↔️ Rules that specify how variables can be replaced

  Start Symbol ↔️ Designated variable that begins string generation
• Terminals in a CFG can be replaced using production rules

  False
• What type of strings does the CFG $S \rightarrow aSa \mid b$ generate?


  Strings with a single b
• Arrange the steps in defining a Context-Free Grammar (CFG)

  1️⃣ Identify the set of variables $V$

  2️⃣ Identify the set of terminals $T$

  3️⃣ Define the production rules $P$

  4️⃣ Choose the start symbol $S$
• Variables in a CFG are also called non-terminals
• Production rules in a CFG specify how variables can be replaced by a combination of variables and terminals
• Which start symbol is used in the CFG $S \rightarrow aSa \mid b$?


  $S$
• The notation for representing CFGs includes four main components
• The terminal symbols in a CFG are represented by the notation $V$


  False
• What type of strings does the CFG S \rightarrow aSa \mid bSb \mid \varepsilon</latex> generate?

  Palindromes
• A derivation in a CFG is a sequence of applying production rules to transform the start symbol into a string of terminals
• A rightmost derivation applies production rules to the leftmost possible variable in each step

  False
• Arrange the steps in a leftmost derivation for the string "aabb" using the CFG $S \rightarrow aSb \mid \varepsilon$


  1️⃣ $S$

  2️⃣ $aSb$

  3️⃣ $aaSbb$

  4️⃣ $aabb$
• What does a parse tree visually represent in a CFG derivation?

  Application of production rules
• Match the derivation types with their definitions:

  Leftmost Derivation ↔️ Applies production rules to the leftmost variable

  Rightmost Derivation ↔️ Applies production rules to the rightmost variable
• What is a derivation in a Context-Free Grammar (CFG)?

  Sequence of rule applications
• In a leftmost derivation, the leftmost possible variable is applied in each step.
• A rightmost derivation applies the rightmost possible variable in each step.
• What does a parse tree visually represent in a CFG?

  Application of production rules
• A CFG is defined by a set of production rules.
• Match the CFG component with its notation:

  Variables ↔️ $V$

  Terminals ↔️ $T$

  Production Rules ↔️ $P$

  Start Symbol ↔️ $S$
• A CFG is formally represented as G = (V, T, P, S)</latex>.
• In CFG notation, $V$ represents the set of non-terminal symbols.
• What are the two types of derivations in a CFG?

  Leftmost and rightmost
• A parse tree's leaf nodes correspond to terminal symbols.
• Parse trees aid in parsing and disambiguation.
• Steps of a leftmost derivation for the string "aabb" using the grammar $S \rightarrow aSb \mid \varepsilon$.


  1️⃣ $S \rightarrow aSb$

  2️⃣ $aSb \rightarrow aaSbb$

  3️⃣ $aaSbb \rightarrow aabb$
• When is a Context-Free Grammar (CFG) considered ambiguous?

  Multiple derivations for a string
• Ambiguity in CFGs can lead to errors in parsing.
• Why is a grammar ambiguous if there are two different parse trees for the same string?

  The string has multiple interpretations
• A CFG is ambiguous if a string can be derived in multiple ways
• What are production rules in a Context-Free Grammar (CFG)?

  Rules for generating strings
• Match the CFG component with its description:

  Variables ↔️ Symbols replaced by production rules

  Terminals ↔️ Symbols in the final strings

  Production Rules ↔️ Specify variable replacements

  Start Symbol ↔️ Initial variable for derivation
• What does the formal notation $G =$$(V, T, P, S)$ represent in a CFG?


  Variables, Terminals, Rules, Start Symbol
• The CFG with $S \rightarrow aSb \mid \varepsilon$ generates strings like "ab", "aabb", and aaabbb
• Terminals in a CFG cannot be replaced by production rules
• What is the purpose of the start symbol in a CFG?

  To begin string generation
• A CFG is formally represented as G = (V, T, P, S)</latex>
• What is a derivation in a CFG?

  Transforming the start symbol