Overview

linear grammar


Show Summary Details

Quick Reference

A grammar in which each production contains at most one nonterminal in its right-hand side. Such a grammar is right-linear if a nonterminal can only occur as the rightmost symbol, i.e. if each production has one of the forms

Aw

AwB

where A and B are nonterminals and w is a string of terminals. A left-linear grammar can be similarly defined:

Aw

ABw

The right- and left-linear grammars generate precisely the regular languages.

The word linear relates to an analogy with ordinary algebra. For example, a right-linear grammar such as

SaSabTabcTabcd

TScSbcTabcabcd

corresponds to the simultaneous linear equations

X= {a}X∪ {ab,abc}Y∪ {abcd}

Y= {Λ,c}X∪ {bc}Y∪ {abc,abcd}

where X and Y are sets of strings and Λ is the empty string. Union and concatenation play roles analogous to addition and multiplication. The smallest solution to the equations gives the language generated by the grammar. See Arden's rule.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.