Skip to main content
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.7k
3 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
  • 934
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.7k
2 votes

Rational subsets of a monoid

Yes, it's a lifting of the monoid product $$x, y āˆˆ M ā†¦ xy āˆˆ M$$ onto a product $$A, B āˆˆ š”“M ā†¦ AB āˆˆ š”“M,$$ that makes the power-set $š”“M$ of $M$ into a monoid, and $M$, itself, a sub-monoid of $š”“M$ ...
NinjaDarth's user avatar
2 votes
Accepted

Regular languages: words from A that do not contain any word from B as a substring

Your language is $A$ intersected with $$\{w\mid \not\exists y\in B\ :\ w=xyz\text{ for some }x,zāˆˆĪ£^āˆ—\},$$ i.e., the complement of $$\{w\mid\exists y\in B\ :\ w=xyz\text{ for some }x,zāˆˆĪ£^āˆ—\}$$ which is ...
user6530's user avatar
  • 934
2 votes
Accepted

Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?

Deciding emptiness of a regular expression is easy, but constructing the complement is not. The paper Succinctness of the Complement and Intersection of Regular Expressions by Gelade and Neven (arXiv:...
Hendrik Jan's user avatar
  • 30.7k
2 votes
Accepted

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

It is indeed regular. Here, your language is basically $1(0+1)^{2m+1}0 + 0(0+1)^{2m+1}1$ for all integers $m \ge 0$. We are basically fixing $\sigma_1 \ne \sigma_3$, and then let $|u\sigma_2v|$ be an ...
codeR's user avatar
  • 706
2 votes
Accepted

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
  • 706
2 votes

Constructing a DFA that accepts the set of binary strings with an even length and an odd number of 1s

let's call first DFA A and second DFA B, let their corresponding states be A.Q and B.Q, then consider $A.Q$x$B.Q$ (cartesian product of states), you will get: $\{(q_e,q_0), (q_e,q_e), (q_0, q_0),(q_0,...
math boy's user avatar
  • 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\}$...
Hendrik Jan's user avatar
  • 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.
gnasher729's user avatar
  • 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 ...
NinjaDarth's user avatar

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