Kontrolltöö "Translaatorite koostamises"  (25.10.99)

Ül. 3.

Selle keele moodustava grammatika produktsioonide hulk on:

{S->A; A->AB; A->BA; A->AAAA; B->BB; B->0; A->1}, kus S on grammatika 
algsümbol.
Nagu näha, vastab antud grammatika produktsioonide hulk kontekstivabale
grammatikale. 

Vastav automaat:

(q0,"1")->qf
(q0,"0")->q0
(q0,"1")->q1
(q1,"0")->q1
(q1,"1")->q2
(q2,"0")->q2
(q2,"1")->q3
(q3,"0")->q3
(q3,"1")->qf
(q3,"1")->q1
(qf,"0")->qf, kus
q0 on automaadi algolek ja qf lõppolek.

UL. 2

EI.
Kuna ühe leheni jõuab mööda tuletuspuu erinevaid oksi läbides see on 
antud produktsioonide puhul võimalik).