## Estimating the range of $1$’s in an array of $0$’s and $1$’s

I have a large array $$A$$ that contains something like $$[0..1..0..]$$. It has a continuous range of $$0$$‘s, followed by a range of $$1$$‘s, and then another range of $$0$$‘s.

This array is large and access is expensive, so I want to use a sampling algorithm to estimate the range $$(i, j)$$, where $$A_i$$ is the first $$1$$ and $$A_j$$ is the last $$1$$. Let’s say I want to approximate this within an error of $$\epsilon n$$ where $$n$$ is the size of $$A$$, so that I get a range $$(i’, j’)$$ where $$|i’ – i| \leq \epsilon n$$ and $$|j’ – j| \leq \epsilon n$$.

What is an algorithm I can use to achieve this?

## Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I’m not looking for the answer, right now I’m just trying to understand the question. I don’t understand what sort of words would be accepted and what would be rejected. For example, I can’t understand whether the following word would be accepted:

011011 ; where 01 is prefix and 1011 is suffix
011011 ; where 011 is prefix and 011 is suffix
011011 ; where 0110 is prefix and 11 is suffix

I guess my question is this: Given a word, how do I know which part is the prefix? I don’t think I can proceed with the question unless this part is clear.

Please try to give an explanation without the actual PDA answer, I’d like to try it myself first.

Thanks!

Posted on Categories proxies

## Context free grammar for language with even number of $0$’s and $1$’s

I want to create a Context-Free grammar that generates the language

$$L = \{ w \in \{0, 1\}^* |\ \text{number of 0 ‘s is even, and number of 1 ‘s is also even} \}.$$

I came up with

$$S \rightarrow 0S0S\ |\ 1S1S\ |\ ABABS\ |\ BABAS\ |\ \epsilon \ A \rightarrow 0A0A\ |\ 1A1A\ |\ 0\ B \rightarrow 0B0B\ |\ 1B1B\ |\ 1\$$

Looks like it does the job, but how can I be sure that it does indeed generate L.

Any help would be appreciated.

Posted on Categories proxies

## Finding a correct regex for the strings with at least two $0s$

I am learning CFGs and before that I’ve made a RE (Regular Expression) for the language of “all strings with at least two $$0$$‘s over the alphabet $$\Sigma = \{0,1\}$$.”

I made this: $$(0+1)^*0(0+1)^*0(0+1)^*$$

I checked the answer and it is: $$1^*01^*0(0+1)^*$$

Is there any difference between the two?

If mine is also correct, what should be the CFG for it?