New answers tagged regular-languages
0
The reverse of a language $L$ is the language $L^R = \{ w^R : w \in L \}$, where $w^R$ is obtained from $w$ by reversing the orders of the letters.
The reverse of a context-free language is context-free. This can be shown by starting with a grammar and reversing all production rules, that is, replacing $A \to \alpha$ by $A \to \alpha^R$. Similarly, the ...
3
When the alphabet is of size $4$ or more, it is easy to prove that $L_4$ is not regular using the pumping lemma. Given a pumping length $n$, let $s$ be a square-free word over $\{0,1,2\}$ of length $n$; such a word exists since there is an infinite square-free word over $\{0,1,2\}$. We choose $w = 3s33s3 \in L_4$. Suppose that we could write $v = xyz$ so ...
2
The automaton accepts exactly the strings that contain exactly one occurrence of $00$ as a substring.
The above is the simplest description of the automaton in English. Note that $00$ substring can be at the very beginning of a string or at the very end of a string.
0
If $n$ is the pumping length and $m = 2^{\left\lceil \log_2 n\right\rceil}$ ($m$ is the smallest power of $2$ greater than $n$), then $z = 0^m$ should do the trick. You need to show that if $z = uvw$ is the pumping decompositon, then one of $uw$ or $uv^2w$ is not in $L_2$.
Top 50 recent answers are included