Задача распознавания цепочек языка.

Задачей распознавания является задача определяющаяся является ли заданная цепочка порождением заданной грамматикой.

R = φψ, гдеφ,ψ € V^*

ώ₁ = ξ₁φ ξ₂= ώ₂ = ξ₁ψξ₂

ξ₁ξ₂ €V* - цепочки

то говорят, что ώ₂непосредственно сворачивается в ώ₁и обозначается ώ₁<= ώ₂ либо

n

ώ₁<= ώ₂

Пусть задано множество цепочек

Ω = { ώ₁ , ώ₂ , ώ₃ , … , ώ_n}

ώ_n-1< = ώ_n

…

ώ₁ <= ώ₂

говорят, что ώ_n<= ώ₁

Если заданная цепочка может быть сведена к начальному символу, то она принадлежит языку, который порождает данную грамматику.