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)