New answers tagged


Treat the DFA like a PDA, and then use some algorithm that transforms PDAs to CFGs.


The language of the grammar is clearly $0^*0$. Hence just build an NFA for this language (which is very easy to do).


There is indeed an extension of regular expressions that accepts the language of two-stack push-down automata, which has the same expressive power as Turing machines. First off, to make the algebra more obvious, I'm going to define the operators using Kleene algebra notation. $0$ is the empty set and $1$ is the zero-length string. Juxtaposition, or $\cdot$, ...


Any language that is accepted by a FSA can be accepted by a regular expression, and vice versa. Any language that is accepted by a Turing machine can be accepted by an unrestricted grammar, and vice versa. See the Chomsky hierarchy. If you literally mean that you just want a string that describes a Turing machine, it is easy to obtain one: convert the ...


I am afraid that "a pair of states repeats" is a little ambiguous. Both computations (from $q_1$ and $q_2$) have to be considered in parallel. So we get a pair of "synchronized" computations $(q_1,q_2), (q^1_1,q^1_2), (q^2_1,q^2_2), \dots, (q_i,q_i)$. If in such a sequence-pair a state-pair repeats we can remove the sequence in between (...


There is a difference between describing the language accepted by an automaton and describing the automaton itself. There can be several different automata that accept the same language. For the particular automaton you give, the language it accepts can be described in plain English as "the set of words that contain at least two 1's separated by at ...


Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang constructed, in their paper Regular Expressions: New Results and Open Problem, a regular expression of size $O(n)$ for which the minimal rejected word has size $\Omega(n2^n)$; here $n$ is an arbitrary parameter. The regular expression can be converted to an NFA with $O(n)$ states and transitions ...


Yup. It looks like this accepts 0011, and it shouldn't, so it looks to me like the automaton is buggy.


If $A$ is the alphabet, $L_1 = LAA$. Now $A$ is finite and thus regular. Thus if $L$ is regular, then $L_1$ is the product of three regular languages and hence is regular. Exercise. Use the same type of argument to show that if $L$ is context-free, then so is $L_1$.


(Note: the below proof may have some issues raised in the comments. I am in the processing of addressing the issues.) The following "end-character" method was suggested in the comment above, as well as private communication with some others. Any mistakes are my own. We construct a polynomial-time reduction from the Gold problem (arbitrary alphabet ...

Top 50 recent answers are included