3.1.2 Jednoznačnost a víceznačnost

Definice (Nejednoznačná bezkontextová gramatika)

Nejednoznačná bezkontextová gramatika

Nejednoznačná (víceznačná) bezkontextová gramatika je taková bezkontextová gramatika \(G\), kde lze pro nějaký řetězec z jazyka \(L(G)\) sestavit alespoň dva různé derivační stromy.

Definice (Jednoznačná bezkontextová gramatika)

Jednoznačná bezkontextová gramatika

Jednoznačná bezkontextová gramatika je taková bezkontextová gramatika \(G\), kde pro všechny řetězce z jazyka \(L(G)\) existuje právě jeden derivační strom.

Definice (Nejednoznačný bezkontextový jazyk)

Nejednoznačný bezkontextový jazyk

Nejednoznačný (víceznačný) bezkontextový jazyk je takový jazyk, kde každá bezkontextová gramatika generující tento jazyk je nejednoznačná (víceznačná).

Neboli neexistuje jednoznačná bezkontextová gramatika, která tento jazyk generuje.

Definice (Jednoznačný bezkontextový jazyk)

Jednoznačný bezkontextový jazyk

Jednoznačný bezkontextový jazyk je takový jazyk, který lze generovat jednoznačnou gramatikou.