User:Ilia Kr./Membership problem

The membership problem for context-free grammar (CFG) can be stated as follows: given CFG $G$ (which generates language $L[G]$) and word $w\in \Sigma ^{*}$, does $w\in L[G]$ hold? That is, can $G$ generate given string $w$?

Showing decidability

via exhaustive search

This problem is decidable via bounded exhaustive search ...

by CYK algorithm

...