11Derivation (Example)Grammar G = ({E), {+,*,(),-,id), P, E) withE→E+Eproductions P=E-E*EE→(E)E→-EE→idExample derivations:E--E--idE=mE+E=mE+id=mid+idE→*EE=*id+idE=+id *id +id
12Chomsky Hierarchy: LanguageClassificationAgrammarGis said tobe-Regular if it is right linear where eachproduction is ofthe formA→WBA→Wororleftlinear whereeachproductionis oftheformA-BWorA-W-Context freeif eachproduction is oftheformA-αwhereAENandaE(NUT)*-Context sensitiveif eachproduction is of theformαAβ→αβwhereAEN,α,,βE(MUT)*,l>0-Unrestricted