# In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex format. can we use $a^n b^n c^n d^n$ format for our guesses?

• The language consisting of all strings of the form $a^nb^nc^nd^n$ isn’t regular! – Yuval Filmus Jul 28 '18 at 16:12

That said, in your case you can emulate a witness of this form. Let’s first replace your $n$ with $m$, reserving $n$ for the input length. Suppose that your algorithm runs in time $t(n)$. Then you can only go through the first $t(n)$ guesses, so without loss of generality you can assume that $m \leq t(n)$. Since $t(n)$ is polynomial, $\log t(n) = O(\log n)$, and so you have enough space on the tape to store $m$. You therefore proceed as follows:
• Guess $m$ (by guessing $\log t(n)$ bits).
• Simulate the guesses $a^mb^mc^md^m$ using a counter that goes up to $m$ and another one that goes up to 4.