0
$\begingroup$

Does the following work and is there anything possibly simpler?

Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$. Intuitively, we want to "remember" (or guess) two states $p$ and $q$ such that $s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$ where $f \in F$ is a valid "run" in $X$ (Also by $\stackrel{w}{\longrightarrow^\ast}$ I mean a transition over letters of $w$).

Consider $X' = \left( Q \times Q \times \left\{ 0, 1, 2 \right\}, \Sigma \cup \{\varepsilon\}, \delta', S, F' \right)$ where $S = \left\{ (p, q, 0) \mid \text{$q$ is reachable from $p$} \right\}$ and $F' = \left\{ (p, p, 2) \mid p \in Q \right\}$. The idea will be to break the automaton into 3 parts joined together by $\varepsilon$-transitions. The transition function is defined as follows: \begin{align*} \delta'\left( (p, q, n), a \right) &= (p, \delta(q, a), n) \quad\forall\, n \in \left\{ 0, 1, 2 \right\}, \\ \delta'\left( (p, f, 0), \varepsilon \right) &= (p, p, 1)\quad\text{where $f \in F$}, \\ \delta'\left( (p, q, 1), \varepsilon \right) &= (p, s, 2). \end{align*} As is evident, we want to store the state $p$ in a ``memory'' throughout any run starting at $(p, q, 0)$. This way, if $s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$ is a valid run in $X$, then we have the following valid run in $X'$ and vice versa: \begin{equation*} (p, q, 0) \stackrel{x}{\longrightarrow^{\ast}} (p, f, 0) \stackrel{\varepsilon}{\longrightarrow} (p, p, 1) \stackrel{y}{\longrightarrow^{\ast}} (p, q, 1) \stackrel{\varepsilon}{\longrightarrow} (p, s, 2) \stackrel{z}{\longrightarrow^{\ast}} (p, p, 2). \end{equation*}

$\endgroup$
2
  • $\begingroup$ If you can prove that it works, then it works. $\endgroup$ Nov 9, 2021 at 7:36
  • $\begingroup$ Thanks @YuvalFilmus, it does seem there is a flaw where I wrote "vice versa": a valid run in $X'$ won't necessarily give a valid run in $X$. I feel storing $q$ in addition to $p$ might be the way to go. $\endgroup$ Nov 9, 2021 at 8:17

1 Answer 1

0
$\begingroup$

You can basically follow the same reasoning without explicitly constructing the resulting finite automaton, using closure properties instead. That might save a lot of technical details. And it makes states $p,q$ explicit, rather than remembering them in states.

Given $X=(Q,Σ,δ,s,F)$ the DFA for $A$, now consider some derived automata that only change initial and final states. Let $X_{pq}=(Q,Σ,δ,p,\{q\}) $ and $X_{pF}=(Q,Σ,δ,p,F) $.

Then $L(X) = \bigcup_{p,q\in Q} L(X_{sp}){\cdot}L(X_{pq}){\cdot}L(X_{qF})$.

The language you are looking for equals $\bigcup_{p,q\in Q} L(X_{qF}){\cdot}L(X_{pq}){\cdot}L(X_{sp})$.

$\endgroup$
2
  • $\begingroup$ This is probably a self-duplicate. I apologize. $\endgroup$ Nov 9, 2021 at 9:52
  • $\begingroup$ Thanks, this looks way more elegant! Hopefully some of my other problems can also be solved in this way. $\endgroup$ Nov 9, 2021 at 10:10

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.