Greibach's theorem is a result in formal language theory, particularly in the context of context-free grammars and the equivalence of certain classes of grammars. Named after Sheila Greibach, the theorem states that for every context-free language, there exists a context-free grammar in Greibach normal form (GNF). A grammar is in Greibach normal form if the right-hand side of every production rule consists of a single terminal symbol followed by zero or more nonterminal symbols.
New to topics? Read the docs here!