A cyclic grammar is one in which there is a derivation A A

A cyclic grammar is one in which there is a derivation A ->* A consisting of one or more steps for some nonterminal A.

a. Show that a cyclic grammar with no useless symbols is ambiguous. (See p. 191 for a definition of useless. [p.191: A nonterminal A is useless if there is no derivation from the start symbol to a string of tokens in which A appears.])

b. Would you expect grammars that define programming languages to be often cyclic? Explain.

Solution

1).in the above derivation a non terminal derives the string *A again it is a nonterminal.

in the grammer any nonterminal symbol that derives non terminal again that will be treated as non terminal and that can not be used in further derivation.

it is an ambigous that for each transition control goes to A for ->* times and control comes againe to A so this makes the cycle..

2).a grammer is infinitly ambigious if it prodeuces an infinite number of parses with some input sentences.
A grammer is cyclic if there exists a nonterminal which can be reduced to it self
if a grammer that can\'t be reduced it self is not used

eg:

A--> A A A

A-> e/€

the above example can be reduced by it self so this kind of reduced grammers can allow in programs but the grammers tha can\'t be reduced are avoided..