Gramatická nejednoznačnost
Definice: Nechť G = (N, T, P, S) je BKG.
Pokud existuje řetězec x Î L(G) s více jak jedním derivačním stromem, potom G je nejednoznačná. Jinak G je jednoznačná.
Definice: BKJ L je vnitřně nejednoznačný, pokud L není generován žádnou jednoznačnou BKG.
Příklad:
• Gexpr1 je jednoznačná, protože pro každé x Î L(Gexpr1) existuje jeden derivační strom
• Gexpr2 je nejednoznačná, protože pro i+i*i Î L(Gexpr2) existují dva derivační stromy
• Lexpr = L(Gexpr1) = L(Gexpr2) není vnitřně nejednoznačný, protože Gexpr1 je jednoznačná
19/50