New answers tagged finite-automata
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
0
votes
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
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
0
votes
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
2
votes
Complexity of deciding if a DFA is counter-free
I've found it in the literature [1], it's PSPACE-complete even for DFAs.
Sang Cho, Dung T. Huynh
Finite-automaton aperiodicity is PSPACE-complete,
Theoretical Computer Science, Volume 88, Issue 1, ...
- 548
Top 50 recent answers are included