A variable-based grammar is a tuple
where and are disjoint finite sets of terminals and variables, , and each production has with at least one variable in .