Uniquely inversible grammar

A uniquely inversible grammar is a formal grammar where no two distinct productions give the same result. This implies the specific production can be inferred from its results.

Formal definition

$A\to \alpha \land B\to \beta \iff (A<>B\Rightarrow \alpha <>\beta )$

Examples

Uniquely inversibles

$A\to aA|bB$

$B\to b|a$

Not uniquely inversibles

$A\to aA|bB$

$B\to bB|a$

This article is issued from Wikipedia - version of the 1/7/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.