# 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
1 vote
Accepted

### Confusion regarding the conversion of epsilon-NFAs to non-epsilon NFAs

It is not clear where you got stuck, but generally speaking, every $\epsilon$-NFA $A = (\Sigma, Q, Q_0, \delta, F)$ can be converted into an equivalent NFA $B$ in polynomial time. Here is one way to ...
• 4,735
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

### Convert finite automaton to regular expression

3rd one will be correct, you can also solve this by minimal sting which is abd and 3rd option is the one that generates abd
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