Due Wednesday, 27 October, 10:10am. Please hand it in to Hossein before the beginning of the exercise session.
A context-free grammar is in Greibach two-standard form if productions are of the following form.
X -> aYZ X -> aY X -> a
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.
Describe why it is not a good idea to use CYK for the arbitrary grammars not in the Chomsky normal form.
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.