There is an extended grammar notation in common use. In this notation, square and curly braces...

Transcribed Image Text:

There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like → or 1) with the following meanings: a. Square braces around a grammar symbol or symbols denotes that these constructs are optional. Thus, production A XIYIZ has the same effect as the two productions A -> XYZ and A -> XZ. b. Curly braces around a grammar symbol or symbols says that these sym-bols may be repeated any number of times, including zero times. Thus, A -> X[YZ) has the same effect as the infinite sequence of productions AX, 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. There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like → or 1) with the following meanings: a. Square braces around a grammar symbol or symbols denotes that these constructs are optional. Thus, production A XIYIZ has the same effect as the two productions A -> XYZ and A -> XZ. b. Curly braces around a grammar symbol or symbols says that these sym-bols may be repeated any number of times, including zero times. Thus, A -> X[YZ) has the same effect as the infinite sequence of productions AX, 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.

Answer rating: 100% (QA)

To show that the extended grammar notation with square and curly braces does not add power to gramma... View the full answer