Extend the idea of Exercise 4.2.4 to allow any regular expression of grammar symbols in the body of a production. Show that this extension does not allow grammars to define any new languages. Exercise...

Extend the idea of Exercise 4.2.4 to allow any regular expression of grammar symbols in the body of a production. Show that this extension does not allow grammars to define any new languages.

Exercise 4.2.4

There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like —>• or |) with the following meanings:

i) Square braces around a grammar symbol or symbols denotes that these constructs are optional. Thus, production A —> X [Y] Z has the same effect as the two productions A X Y Z and A -± X Z.

ii) Curly braces around a grammar symbol or symbols says that these symbols may be repeated any number of times, including zero times. Thus, A —>• X {Y Z} has the same effect as the infinite sequence of productions A-*X,A->XYZ,A-*XYZYZ, and    so      on.

Show that these two extensions do not add power to grammars; that is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.