A language can be generated by one of these constructs if any string in the language can be broken up into five separate substrings that pass three different criteria, such as having the three middle substrings combined being less than the "pumping length." That version of the pumping lemma for languages generated by these can be proven through the use of derivation trees generated by these constructs. The CYK algorithm can be used to determine if a string can be generated by one of these, and an alternate form of representing them is the Greibach Normal Form, which is used in showing that these constructs are equivalent to push-down automata. Defined by terminal and nonterminal alphabets, production rules, and a start symbol, for 10 points, name this type-2 grammar which can generate languages more powerful than regular ones but not as p
A language can be generated by one of these constructs if any string in the language can be broken up into five separate substrings that pass three different criteria, such as having the three middle substrings combined being less than the "pumping length." That version of the pumping lemma for languages generated by these can be proven through the use of derivation trees generated by these constructs. The CYK algorithm can be used to determine if a string can be generated by one of these, and an alternate form of representing them is the Greibach Normal Form, which is used in showing that these constructs are equivalent to push-down automata. Defined by terminal and nonterminal alphabets, production rules, and a start symbol, for 10 points, name this type-2 grammar which can generate languages more powerful than regular ones but not as powerful as context-sensitive ones, developed by Noam Chomsky.
A language can be generated by one of these constructs if any string in the language can be broken up into five separate substrings that pass three different criteria, such as having the three middle substrings combined being less than the "pumping length.
{C}{ontext-}{f}{ree }{G}{rammars} [prompt on {P}{ush-}{d}{own }{A}{utomata }or{C}{ontext-}{f}{ree }{L}{anguages}]