New answers tagged 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
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
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