Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

New answers tagged

0 votes

Is the language of words containing equal number of 001 and 100 regular?

Several years ago I and several colleagues generalized when the language of all strings with equal number of $x$ and $y$ substrings over an alphabet $\Sigma$ is regular: https://arxiv.org/abs/1804....
Ryan Dougherty's user avatar
0 votes

$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

The question is now 2 years old, but whatever. Here is a very simple family of counterexamples. On the alphabet $\{a,b\}$, let $L_k$ comprise the words with the same number of $a$'s and $b$'s or ...
Arnaldo Mandel's user avatar
0 votes

Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language

After processing $a^r b^q c$ only a string of exactly (q - 1) c's will lead to an accepting state. So for every q, you must end up in a different state after processing $a^r b^q c$, which means the ...
gnasher729's user avatar
  • 30.4k
2 votes

pumping lemma, concatenation of non-regular languages $a \neq b$

The following is not a proof. It convinced me, but perhaps your professor does not accept proof-by-picture. Draw stings over $\{a,b\}$ on the grid. For $a$ go up, for $b$ go down. Any string in $L_{a\...
Hendrik Jan's user avatar
  • 30.8k
4 votes
Accepted

pumping lemma, concatenation of non-regular languages $a \neq b$

Even if it seems strange, actually the language $L=L_{a \neq b} \circ L_{a \neq b}$ is regular, moreover, if $\Sigma=\{a,b\}$, then $L$ is "almost" $\Sigma^+$ (note that $\epsilon \not\in L$)...
user6530's user avatar
  • 954

Top 50 recent answers are included