Context-free languages study guide

1. Read the notation precisely

Separate the roles of the symbols before attempting a question. A name such as <expression> is a non-terminal: it is a placeholder for a structure still to be expanded. Quoted symbols such as "(" and ")" are terminals: they are part of the final string. ::= introduces a definition, while | separates alternatives. Symbols written beside one another are normally required in sequence.

For example:

text <list> ::= <number> | <number> "," <list>

This rule permits a single number or a number followed by a comma and another list. It can therefore generate 4, 4,7, and 4,7,9. It does not generate 4, because the second alternative requires another <list> after the comma.

2. Use a systematic syntax-checking method

When checking a proposed string, use these steps:

1. Identify the start non-terminal, normally the left-hand side of the main rule.
2. Select an alternative that might produce the beginning of the proposed string.
3. Replace one non-terminal at a time, keeping the order of terminals visible.
4. Continue until either the exact string is produced or no rule can match the next symbol.
5. Confirm that no non-terminals or unconsumed characters remain.

For the grammar above, consider 4,7. Start with <list>. The single-number alternative cannot consume the comma, so select <number> "," <list>. After deriving 4 as the first number, the remaining input is ,7; the comma is consumed and the final <list> derives 7. The complete string is therefore valid.

For 4,,7, the first number and comma may be matched, but the next <list> must begin with a <number>, whereas the next character is another comma. The derivation fails, so the string is invalid.

3. Formulate simple production rules

Start by describing the smallest valid case. Then add an alternative or recursive continuation for a longer case. For a sequence of one or more x symbols, a suitable rule is:

text <sequence> ::= "x" | "x" <sequence>

The first alternative supplies the smallest sequence, x. The second allows another x followed by a sequence, producing xx, xxx, and longer strings. A useful check is to test both the shortest valid string and a longer valid string, then test a string containing an incorrect symbol.

If the required structure has matching delimiters, put the recursive non-terminal between the delimiters:

text <group> ::= "a" | "(" <group> ")"

This generates a, (a), and ((a)). The placement of <group> is what creates nesting. A rule that merely repeats a fixed sequence would not provide the same recursive structure.

4. Explain the distinction from regular expressions

A strong explanation should identify the structural feature, not merely state that BNF is “more powerful”. BNF can include recursive productions. Recursion allows one valid structure to contain another structure of the same kind, with no fixed maximum nesting depth in the rule. Correctly nested delimiters require the opening and closing symbols to correspond across these levels. Regular expressions can describe repeated or alternative patterns, but they cannot represent arbitrary matching and nesting of this type. Consequently, some languages described by recursive BNF cannot be represented by regular expressions.

5. Applying syntax diagrams

Treat a syntax diagram as a route-selection problem. Follow the path from its start to its end, taking one branch when an alternative is presented and repeating a loop only when the next input symbols support another repetition. Check that the entire input is consumed. Do not assume that reaching the end of one branch validates the whole string if characters remain afterwards.

6. Self-check questions

• In <thing> ::= "a" | "b", what does the vertical bar mean?
• What is the difference between a terminal and a non-terminal during a derivation?
• Can <list> ::= <number> | <number> "," <list> generate 8,3,1? Show the sequence of choices.
• Why does the recursive group rule generate nested parentheses?
• Why is arbitrary nesting the key reason that BNF can represent some languages that regular expressions cannot?

For each answer, include the rule or derivation that justifies your conclusion. If a string is rejected, identify the exact point at which the next input symbol cannot be produced. This is more reliable than judging validity from appearance alone.