2

Let $ A, B \subset \{ a, b\}^* $ and $A, B$ be regular. Lets define: $ A \circ B = \{ w \in A | \exists y \in B , \#_aw = \#_ay \}$ where,for example: for $ w = aaabaaba$

$\#_aw = 6, \#_bw = 2 $ Prove, that $A \circ B $ is regular.

My idea: Let modify DFA for $B$. ($DFA(B)$).

The only modification is function: $f'(q, a) = \{ f(q,a) , q) \}$

In words, after reading $a$ we are stay at the place $(f'(q,a) = q)$ and behave normally( $f'(q,a ) = f(q,a)$)

Now, we take a product of DFA(A) and modified DFA(B).

Please mark.

user180834
  • 1,453

1 Answers1

1

Suppose that $A=\{a\}^*$ and $B=\{b\}^*$, so that $A\circ B=\{\lambda\}$. Let $M$ be the DFA with states $q_0$ and $q_1$, with $q_0$ as initial state and the only acceptor state, and the transition function shown below:

$$\begin{array}{c|cc} &a&b\\ \hline q_0&q_1&q_0\\ q_1&q_1&q_1 \end{array}$$

Clearly $M$ accepts $B$. Your modification would make it an NFA with the following transition function:

$$\begin{array}{c|cc} &a&b\\ \hline q_0&\{q_0,q_1\}&\{q_0\}\\ q_1&\{q_1\}&\{q_1\} \end{array}$$

This NFA accepts $\{a,b\}^*$, so its product with a DFA accepting $A$ will accept $A$, not $A\circ B$.

Here’s a suggestion. Start, as you did, with a DFA $M$ accepting $B$, but modify it differently. For each state $q$ of $M$ let $Q_q$ be the set of states of $M$ that can be reached from $q$ by some $b^mab^n$ with $m,n\ge 0$. If $\delta$ is the transition function of $M$, modify it so that $\delta'(q,a)=Q_q$ and $\delta'(q,b)=\{q\}$.

Brian M. Scott
  • 616,228