3
$\begingroup$

let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$.

I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ is regular for every $p\in Q$ by defining an automaton $A_p$.

I tried to define it like so $$A_p=\{\Sigma, Q\times Q, (p, q_0), F\times \{p\}, \delta_p\}$$ where $\delta_p$ is defined like so $$ \delta_p((q_1, q_2), \sigma) = (\delta(q_1, \sigma), q_2)\text{ if }q_1 \not\in F, \\ \delta_p((q_1, q_2), \sigma) = (q_1, \delta(q_2, \sigma))\text{ if }q_1 \in F. $$ But then I have a problem where $x=uv$, $\delta(p, u)\in F$ and $\delta(p, x)\in F$.

I thought maybe I define $A_p$ as a non-deterministic automaton and then $$\delta_p((q_1, q_2), \sigma) = \{(\delta(q_1, \sigma), q_2), (q_1, \delta(q_2, \sigma))\}.$$ However, word $z=uwv$ where $$\delta_p((p, q_0), u) = (p_1, q_0) \Longrightarrow \delta_p((p_1, q_0), w) = (p_1, p) \\ \Longrightarrow \delta_p((p_1, p), v) = (p_2, p), p_2\in F\times \{p\}$$ is accepted while it shouldn't be part of $L_p$

$\endgroup$
2
  • $\begingroup$ Your language $L_p$ is the concatenation of the languages accepted by the automata $A_1=(\Sigma,Q,p,F,\delta)$ and $A_2=(\Sigma,Q,q_0,\{p\},\delta)$. Hence the construction you need is that of concatenating two automata. In this case with an extra step to make the state spaces disjoint. $\endgroup$ Apr 20 at 11:17
  • $\begingroup$ Crosspost with this question on Math.StackExchange. $\endgroup$
    – J.-E. Pin
    Apr 22 at 12:37

1 Answer 1

1
$\begingroup$

Since how a word $w$ is recognized as a member of $L_p$ depends on a successful choice of partition of $w$ into a prefix ($x$) and a suffix ($y$) among many possible partitions, a DFA with $\epsilon$-moves that accepts $L_p$ should be easier to build than a DFA.

To distinguish whether a symbol is used as in $x$ or in $y$, we can employ two copies of $A$, one copy for reading $x$ and one copy for reading $y$. When the state after reading some $x$ is one of the final states of the first copy, switch to the initial state $q_0$ of the second copy optionally, continuing reading the remaining $y$. At the end of reading all input, accept if the second copy is at state $p$.

Two copies of $A$ can be built on the cartesian product $Q\times \{1,2\}$, where the copy index $1$ and $2$ indicates which copy of $A$.

Here is a DFA with $\epsilon$-moves that accepts $L_p$.
$D_p=\{\Sigma, Q\times\{1,2\}, (p, 1), \{(p,2)\}, \mu\}$, where $\mu$ is defined below. $\quad\mu((q,1), \sigma) = (\delta(q, \sigma), 1)\quad\forall q \in Q,\ \sigma\in\Sigma,$
$\quad\mu((q,2), \sigma) = (\delta(q, \sigma), 2)\quad\forall q \in Q,\ \sigma\in\Sigma,$
$\quad\mu((f,1), \epsilon) = (q_0, 2)\quad\forall f \in F.$
Note that when the copy index is fixed, $D_p$ behaves exactly as $A$.

$\endgroup$

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.