4
votes
Accepted
$L'=\left \{ z^Rx : xyz\in L \right \}$ is regular
Let $A = (\Sigma, Q, q_0, \delta, F)$ be a DFA that recognizes $L$. For states $p, q\in Q$, let $A_{p, q}$ denote the DFA obtained from $A$ by letting $p$ be the initial state and $q$ be the only ...
- 4,735
3
votes
Accepted
Myhill-Nerode sentence and the relation $R_L$
Note that $u, v$ and $w$ can contain any letter. Therefore, $L$ is the language of all words that contain some letter at least twice. In particular, a word that contains some letter 3 times is in $L$. ...
- 4,735
Only top scored, non community-wiki answers of a minimum length are eligible