theory of computation

Question

Show that there exists an algorithm to determine whether the language generated by some context-free grammar contains any words of length less than some given number n.

Answer 1

Yes there exist an algorithm i am going to show you an worst case approach for it.

1) let $\sum$ be set of finite input symbol

so we an enumerate all the possible string  length n-1

2) now we will generate set of all strings of length n-1 generated bu given grammar

3) We have two different set now and just have to apply string matching algorithm.

Eg let $\sum ={a,b}$ and n=3

so set 1={$\epsilon$,a,b,aa,ab,ba,bb}

CFG is S->aSb|$\epsilon$

Set 2={$\epsilon$,ab}

apply string matching and result will be ={$\epsilon$,ab}