For regular languages $A,B\subseteq\{0,1\}^*$, is

$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$

regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?

i need to demonstrate $L_2$ automata.

Thought about using the multiplication automata, not so sure.

  • $\begingroup$ Oops, I misread the question, ignore my previous comment. $\endgroup$ – SergGr Dec 2 '18 at 22:09
  • $\begingroup$ Is it enough to just prove $L_2$ is regular? $\endgroup$ – John L. Dec 3 '18 at 4:18
  • $\begingroup$ @Apass.jack yes this is fine $\endgroup$ – Maor Rocky Dec 3 '18 at 5:45

The idea is as follows:

  • We run two automata in parallel: one verifies that the input is in $A$, and the other verifies the other condition.
  • The second automaton simulates an automaton for $B$, in the following way. At any point in time it may simulate reading a $0$. It ignores all $0$s in the real input, and forwards all $1$s in the real input.

I'll let you construct an NFA given this description.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.