BNF and Context-Free Languages

Backus–Naur Form uses non-terminal names for expandable syntactic categories and terminals for literal symbols in the generated language. A production such as <bit> ::= 0 | 1 defines two possible terminal replacements. Start from the designated start symbol and repeatedly apply allowed productions.

A derivation is successful when only terminals remain and they match the input exactly. Angle brackets and the production separator are notation, not necessarily characters in the recognised string. State any convention for the empty string explicitly, because grammars use different symbols for it.

The rules <word> ::= <bit> | <bit><word> and <bit> ::= 0 | 1 generate non-empty binary strings. The first alternative ends the expansion; the second extends it. A grammar with no terminating route might repeatedly expand without producing a finite valid string.

For a block of n zeroes followed by n ones, n≥1, a rule S ::= 0 S 1 | 01 pairs each added leading zero with a trailing one. It generates 01, 0011 and 000111. It does not mean every arbitrary ordering with equal counts, such as 0101.

A context-free grammar can express recursive nesting or matching counts that a finite state machine cannot track without a bound. BNF can therefore represent some languages that formal regular expressions cannot. It can also describe regular languages, as the simple binary-word example shows.

Passing a syntax rule does not prove semantic correctness. A structurally valid expression might still use an undeclared name or divide by zero. In an exam, show the specific derivation or failing production rather than stating that a string “looks like code”.

<integer> ::= <digit> | <digit><integer>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.