New answers tagged

1 vote

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

Basically, your language asks you to restrict the run length of 1s to at most three. Here's how you can construct the required regex: Step 1: Construct a DFA $M$ that accepts all strings that have at ...
codeR's user avatar
  • 634
3 votes

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 ...
Nathaniel's user avatar
  • 15.6k
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 ...
NinjaDarth's user avatar
0 votes

Finding the Smallest Language Class containing a given language definition

The regular languages are indeed closed under the Right Quotient (RQ) operation. That is $RQ(L_1,L_2)$ also written as $L_1/ L_2$ is regular when both $L_1$ and $L_2$ are regular. The proof here (see ...
codeR's user avatar
  • 634
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\}$...
Hendrik Jan's user avatar
  • 30.6k
2 votes

Resources on Tree Automata Regular Expressions

Here is a master's thesis and an arXiv paper on the topic, which contains some examples.
codeR's user avatar
  • 634
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.
gnasher729's user avatar
0 votes

NFAs that accept a regular language

The "corresponding NFA", as you call it, for $a^+ ∪ (ab)^+$ is not your $$→ q_0,\quad q_0 \overset{a}→ q_0,\quad q_0 \overset{a}→ q_1,\quad q_1 \overset{b}{→} q_2,\quad q_1 →,\quad q_2 → q_0,...
NinjaDarth's user avatar

Top 50 recent answers are included