Lukas' Notes

Reduced Context-Free Grammar

May 01, 20261 min read

languages

Definition

Reduced Context-Free Grammar

A context-free grammar is called reduced if it contains no

  • useless productions,
  • epsilon-productions, and
  • unit productions.

Equivalently, every non-terminal symbol is reachable from the start symbol and derives at least one word in terminal symbols.

Every context-free grammar can be transformed into an equivalent reduced grammar, provided the grammar does not need to generate the empty word.


Graph View

Backlinks

  • 192.017 Theoretical Computer Science

Created with Quartz v4.4.0 © 2026

  • GitHub