Tag Info

Hot answers tagged


This is either trivial or hugely difficult, depending on exactly what it means to "represent" a language "as math". In both directions it seems like you should know more about this than we do. I mean as I type this various English words are being represented as sequences of integers inside this machine - is that "representing" English "as math"? On the ...


The language is regular. It’s the union of the following four languages, each of which is clearly regular: $$\begin{align*} L_1=\left\{00z00:z\in\{0,1\}^+\right\}\\ L_2=\left\{11z11:z\in\{0,1\}^+\right\}\\ L_3=\left\{01z10:z\in\{0,1\}^+\right\}\\ L_4=\left\{10z01:z\in\{0,1\}^+\right\}\\ \end{align*}$$ The problem with your pumping lemma argument is that ...

Only top voted, non community-wiki answers of a minimum length are eligible