# Tag Info

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

### Myhill-Nerode sentence and the relation $R_L$

Look at a string x. If x contains some letter twice, then xy is in the language for every string y. Or x consists of k different letters in any order. Then xy is in the language if either y contains ...
• 31.4k
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
1 vote
Accepted

### What is the connection between a regular language's pumping number, and the number of states of an equivalent deterministic automaton?

Usually, we care about a pumping constant as the size of every automaton (including nondeterministic ones) for the language can be used as such. If your goal is to find the minimal natural $p$ that ...
• 4,735