2.5 Decision Algorithms
Given CFL L and string w, check if w in L
convert L to CNF. We know binary tree of height n has at least n+1 leaves. Find all parse tree with height |w|, then we will find all strings in L such that with length less or equal to |w|. Go through all these strings and check if w belongs to them.
Decide if a given CFL is empty or infinite
Mark all nullable symbols, if S is marked then CFL is empty.
Convert L to CNF. If CFL is finite, there should not be any repeated symbols along a path of any parse tree of any string. So just check find all parse tree with height from l to 2l where l is the number of non-terminal symbols in grammar. If we could find at least one, then this CFL is infinite.
Problems that are not decidable
- two CFL is the same
- intersection of 2 CFL is empty
- a CFL
- a given grammar unbiguous
- a given language inheritantly unbiguous(all possible parse tree unbigous)