edited by
459 views
0 votes
0 votes

 There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like $\rightarrow$ or $\mid$) with the following meanings:

  1. Square braces around a grammar symbol or symbols denotes that these constructs are optional. Thus, production $A\rightarrow X [Y] Z$ has the same effect as the two productions $A\rightarrow X Y Z$ and $A\rightarrow X Z$.
  2. Curly braces around a grammar symbol or symbols says that these symbols may be repeated any number of times, including zero times. Thus,$A\rightarrow X \{Y Z\}$ has the same effect as the infinite sequence of productions $A\rightarrow X,A\rightarrow X Y Z,A\rightarrow X Y Z Y Z$,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.    

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
admin asked Aug 17, 2019
406 views
The grammar in Fig. $4.7$ generates declarations for a single numerical identifier; these declarations involve four different, independent properties of numbers.Generaliz...