patternMinor
For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?
Viewed 0 times
xyzregularforlanguage
Problem
For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?
[Where $w^R$ is the reverse of $w$]
My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language.
Any hints?
[Where $w^R$ is the reverse of $w$]
My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language.
Any hints?
Solution
Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$.
It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.
It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.
Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.
It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.
It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.
Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.
Context
StackExchange Computer Science Q#74600, answer score: 8
Revisions (0)
No revisions yet.