про кс-грамматику: ссылка

про дерево вывода и однозначность: ссылка

КС-грамматика

Определение

Грамматика G наз-ся контестносвободной (далее везде будет сокращение: КС ), если все её правила вывода имеют вид $A \to \alpha$

Определение

Язык L наз-ся КС, если существует КС-грамматика, которая его пораждает.

#Пример

$S \to aSb|ε$ порождает $\{ a^nb^n | n≥ 0 \}$ и он является КС

#Пример 1

Грамматика порождает язык Дика

$S \to ε \ | \ () \ | \ SS \ | \ (S)$

#Пример 2

Арифметические выражения

$S \to x \ | \ S + S \ | \ S * S \ | \ (S)$

#Пример 3

$S \to if \ E \ then \ S \ | \ x$

$E \to E \ or \ b \ | \ b$

#Пример 4

$\alpha = \{ a^n b^n c^n \ | \ n ≥ 0 \}$ - не КС

$S \to S'M$