Exercise 4.2.8 from "Compilers - Principles, Techniques, & Tools" (a.k.a. Dragon Book)

I have been banging my head on this problem for a while.

This is the text of the exercise:

The grammar in Fig. 4.7 generates declarations for a sin­gle numerical identifier; these declarations involve four different, independent properties of numbers.

stmt -> declare id optionList
optionList -> optionList option | ε
option -> mode | scale | precision | base
mode -> real | complex
scale -> fixed | floating
precision -> single | double
base -> binary | decimal

1) Generalize the grammar of Fig. 4.7 by allowing n options Ai, for some fixed n and for i = 1,2... ,n, where Ai can be either ai or bi· Your grammar should use only 0(n) grammar symbols and have a total length of productions that is O(n). 2) The grammar of Fig. 4.7 and its generalization in part (a) allow declarations that are contradictory and/or redundant, such as

declare foo real fixed real floating

We could insist that the syntax of the language forbid such declarations; that is, every declaration generated by the grammar has exactly one value for each of the n options. If we do, then for any fixed n there is only a finite number of legal declarations. The language of legal declarations thus has a grammar (and also a regular expression), as any finite language does. The obvious grammar, in which the start symbol has a production for every legal declaration has n! productions and a total production length of O(n x n!). You must do better: a total production length that is O(n2^n) Show that any grammar for part (b) must have a total production length of at least 2^n.

In particular, I am stuck on part 2. I know that given n binary options, setting an option to a_n or b_n results in 2^n combinations. What I don't know is how to express this without mentioning the position of each option.

I.e., how do I come up with a grammar where I can specify any A1...AN options, without expressing all the N! combinations (e.g., for A1, A2 and A3: A1 A2 A3, A1 A3A 2, A2 A1 A3, A2 A3 A1, A3 A1 A2, A3 A2 A1 )?

Thanks

Instead of trying to write a grammar, we could just create a finite-state machine (which, as we know, is equivalent for a regular grammar). It should be clear that in this finite-state machine, each state will correspond to some subset of the n attribute types, and all of its valid transitions will be to states which represent a subset with exactly one more attribute type. (All of the states are accepting, since there is no minimum number of attributes.) So for the grammar with four attribute types (the original grammar), we end up with 16 states:

To convert that to a grammar, we only need to make each state a non-terminal, and each edge a production. Since there are never more than n transitions from any node, the total number of edges (and hence productions) is less than n·2ⁿ. (In fact, there are exactly n·2^n-1 transitions in the state machine.) Furthermore, every production right-hand side has at most two symbols.