Complexity of advice language? Let $L$ be a language in P/poly.  There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$.  Consider the language $A(M)$ of all advice strings given to $M$ for instances in $L$.


  Is $A(M)$ in P/poly?


Edit 2: For $A(M)$ I am envisaging a specific, unique advice language; the existence of some advice language is guaranteed by the definition of $L$, so for $A(M)$ pick any such language, such as the lexicographically smallest.  Note that $A(M)$ is not necessarily decidable.

A handwaving (non-)argument for believing this goes something like this.  Every unary language is in P/poly, since a single bit of advice is enough to indicate whether the input is in the language or not.  In some sense advice languages are "sparsifications" of their associated languages; the advice language $A(M)$ contains a sparser representation of some of the information contained in language $L$, tweaked for the specific machine $M$.  (The advice language could be exponentially sparser, if every string is an instance of the problem, but for sparse languages the advice language may actually be polynomially denser.)  So it would seem to make sense that sparsifications of languages in P/poly could also be in this class.

Moreover, is there a general relationship between the complexity of $L$ and that of $A(M)$?

These seem like basic questions, so pointers to relevant literature would be appreciated if these are well-known.  A counterexample for the handwaving above would also be useful!

Edit: removed a sentence that wasn't even wrong, and based on the comments from Robin and Tsuyoshi, redefined the advice language to depend on $M$ only, as $M$ already depends on $L$.

Edit 3: I think Hrushikesh captured the essential problem here, so I am accepting the answer; Tsuyoshi also said essentially the same thing in a comment.  In short, $A(M)$ can be arbitrary.  Any language can be fed as advice to $M$ by waiting until the input instances of the decision problem are large enough for the next piece of advice to be within the polynomial bound.  This also means that I should really have asked the question in terms of a decision problem (where there are both YES and NO instances), not a language, to avoid the case where there are only finitely many YES instances.
Rigorous and probably more correct version at the bottom.

I don't think so. Consider the case where A(L,M) consists of advice strings of even length. To decide if x is in L, the machine M gets advice yz where y and z are strings of equal length. M discards z and decides membership of x in L only depending on y. Let y be of length n, and let z range over some arbitrary subset S of strings of length n.

In such a case, A(L,M) cannot be in P/Poly since given a string yz, the machine has to test membership of z in S. But since the advice is of length poly(n), the machine cannot work correctly for every S by counting argument.

Another more rigorous version:

Let L be the trivial language containing all strings. The machine M ignores its advice and accepts every input. The task is now to construct the set of advice strings A(M) which cannot be in P/Poly subject to the constraint that strings in L of length $n$ get advice of length $O(poly(n))$.

For every length $i$, let $S_i \subseteq {0,1}^i$. Let $S = \cup_i S_i$. Construct a mapping $f: S \rightarrow Z^+$ such that $|s| \leq f(s)$. The mapping just enumerates the strings in $S$ in non-decreasing order of length. The string $s$ serves as advice to M for strings of length $f(s)$. 

By choosing $S_i$ to be of superpolynomial description size (can be done because of counting arguments), we get that $S$ (which is also $A(M)$) lies outside P/Poly.