When we diagonalize, the result on the diagonal could be in one of the rows
below.
Section 11.2
1. Look ata typical derivation:
From this it is not hard to conjecture that the grammar derives
3. Formally, the grammar can be described by G = (V,S,T,P), with
and
The unrestricted grammars in Definition 11.3 are equivalent to this
extension because to any given unrestricted grammar we can always add
starting rules S 0 → s i for all s i ∈ S.
7. To get this form for unrestricted grammars, insert dummy variables on the
right whenever |u| > |v|. For example,
can be replaced by
below.
Section 11.2
1. Look ata typical derivation:
From this it is not hard to conjecture that the grammar derives
3. Formally, the grammar can be described by G = (V,S,T,P), with
and
The unrestricted grammars in Definition 11.3 are equivalent to this
extension because to any given unrestricted grammar we can always add
starting rules S 0 → s i for all s i ∈ S.
7. To get this form for unrestricted grammars, insert dummy variables on the
right whenever |u| > |v|. For example,
can be replaced by