# Tag Info

### NFA for a regular expression without $\epsilon$-transitions

You can convert the regular expression into an automaton using the Glushkov's construction. The resulting automaton is non-deterministic and does not contain any $\varepsilon$-transition. Its number ...
• 15.7k
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$)...
• 934

• 357
1 vote

### Finding the Smallest Language Class containing a given language definition

The question is about closure properties of regular languages. In your question it is asked what is the family tho which the quotient $RQ(L_1, L_2) = \{ w \mid wv \in L_1 \text{ for some } v \in L_2\}$...
• 30.7k
1 vote

### Can this Classic Regular Expression be simplified?

$(\Sigma \Sigma)^* (\Sigma 0 0 | 0 0 \Sigma) (\Sigma \Sigma)^*$ You need an even number of letters on the left and an odd number on the right, or the other way round.
• 30.1k
1 vote

### Regular expression vs rational expression

The usage that I've seen, have been told of, and that I recommend is "rational" if the underlying monoid is non-free, "regular" for free monoids. Examples showing this, which I've ...
• 339

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