Sequences and Languages

Question

Let $U$ be the following language. A string $s$ is in $U$ if it can be written as:

$s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$,

where $a_1,..., a_n$ are positive integers such that there is a 0-1 sequence $x_1, ..., x_n$ with $x_1a_1 + ... + x_na_n = b$. Show that $U \in P$.

Not sure how to even approach the problem. Any help would be appreciated. I dont want the answer specifically, but any hints or help would be great.

Thanks

Answer 1

If I’ve understood the description of $U$ correctly, it’s context-free, and all context-free languages are in $P$. I’ve spoiler-protected a context-free grammar for it below.

Initial symbol $S$, productions $S\to A\mid B$; $A\to 1X1$; $X\to 1X1\mid 0A\mid 0B\mid 0$; $B\to 1Y$; and $Y\to 1Y\mid 0A\mid 0B\mid 0$.

Answer 2

Hint for constructing a pushdown automaton recognising your language $U$ by empty stack:

[I didn't re-read the question before writing this, so I forgot the $a_i$'s had to be positive. You have to make a slight modification, probably adding two extra states, because of that, but the basic idea is still the same.]

Use three states apart from the initial state: two ($p_0$ and $p_1$) to indicate whether the current $x_i$ is $0$ or $1$, and one ($b$) to indicate that we are guessing we're up to the $1^b$ part. We only need one stack symbol, which we use to count the $1$s we read in $p_1$ and then check them off against the $1$s we read in $b$.

The fact that context-free languages are in $P$ is well-known, but I suppose if you haven't covered it in your course and this is homework, I guess you will need to convert either the pushdown automaton or the grammar into a polynomial-time Turing machine (which is easy to do).