Due Monday, 24th October, 10:15am. Please hand in before the lecture.
A grammar has a cycle if there is a non-terminal such that , i.e. it is possible to derive the nonterminal A from A by a sequence of production rules.
Show that if a grammar is in Chomsky normal form then the parse tree for a word of length has exactly interior nodes.
Assume a grammar in Chomsky normal has non-terminals. Show that if the grammar can generate a word with a derivation having at least steps, then the recognized language should be infinite.
Assume that we want to use the CYK algorithm for the grammars which are not in Chomsky normal form. For example, consider the following grammar for balanced parenthesis:
S -> ( S ) S -> SS S -> ()
The diagram below shows the parsing for "(()())" using CYK.
What is the complexity of the CYK algorithm in this case? Describe why it is not a good idea to use CYK for arbitrary grammars not in the Chomsky normal form.
Let {a, b} be terminals, and {A, B} non-terminals. A production is called linear if it is of the form A → aBb. In other words, if the right hand side can contain only one non-terminal. Show that there are context free languages for which no linear grammar exists.