OurBigBook.comSite Source code

Concatenation grammar

For grammars

G = (Σ, V, P, S)

and

G^{'} = (Σ, V^{'}, P^{'}, S^{'})

with disjoint variable sets, introduce a new variable

S_{0}

and set

H = (Σ, V \cup V^{'} \cup {S_{0}}, P \cup P^{'} \cup {S_{0} \to S S^{'}}, S_{0}) .

If both input grammars are variable based, then

L (H) = L (G) L (G^{'})

.

Table of contents 147 3
- Regular concatenation grammar Concatenation grammar 89 1
  - Failure of the regular concatenation construction for a nonregular grammar Regular concatenation grammar 42
- Concatenation grammar need not be regular Concatenation grammar 27

 Ancestors (7)

 Incoming links (1)

Solution