# Tag Info

Accepted

### Is the language given by the regex (ab)* star-free?

No. $L=(ab)^*$ is star-free. A word is in $L$ iff It starts with $a$ (or is empty) It ends with $b$ (or is empty) It does not contain any consecutive $a$'s It does not contain any consecutive $b$'s ...
• 159k

### Notation in NFA, DFA diagrams and language

You need to distinguish between three kinds of operations: Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer ...
• 5,539
Accepted

### How to show L is non-regular without pumping lemma?

Well, you can't show that it is not regular, because it is regular. Indeed, $L = (ab)^*\setminus \{(ab)^6\}$, and $(ab)^*$ is regular (concatenation + kleene star), and $\{(ab)^6\}$ is regular (...
• 15.6k

### Proof that a union of two non-regular languages may be regular

Let $L_2 = A^* \setminus (L_1\cup \{\varepsilon\})$. Then $L_1 \cup L_2 = A^*\setminus \{\varepsilon\}$ which is regular and not equal to $A^*$.
• 15.6k
Accepted

### What does empty string ε actually mean?

Regular expressions represent sets of strings, so $\varepsilon$ in that expression represents the set that contain only the 0 length string, $\{\varepsilon\}$. This of course is not the same as the ...
• 2,745

### Notation in NFA, DFA diagrams and language

Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^* = \bigcup\limits_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the ...
• 2,921

• 39k
Accepted

### Proving the set $R$ is finite

There exists an infinite sequence of strings, such that no string is a substring of another. For example $a b^* a$. If one considers the subsequence ordering instead of the substring ordering, then ...
• 30.6k

### Proof that a union of two non-regular languages may be regular

If you don't want $L_2$ to be the complement of $L_1$ (as then $L_3$ would the set of all words), then you can simply choose $L_2$ to be $\overline{L_1}\setminus L$, where $L$ is a nonempty finite ...
• 2,921
Accepted

### How to handle multiple exponents (Pumping-Lemma)

There is actually a more generalized version of the pumping lemma, where you can pump a substring anywhere in the word. The proof is almost the same: in a computation of a word $w$ in a DFA, if there ...
• 15.6k

### How to handle multiple exponents (Pumping-Lemma)

There is a solution to your pumping problem using the classical formulation of the Pumping Lemma, writing $w=xyz$ and considering $|xy| \le p$ and $xy^iz$ for $i\ge 0$. The trick is pumping down... ...
• 30.6k

### 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.6k
Accepted

### Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$

To show that a language $L$ is not regular you need to argue that the pumping lemma does not hold. That is, you want to show that for every $p$, there exists some word $w$ such that, for every ...
• 29.5k

### 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$ ...
• 314
Accepted

### Counting States in the trim automaton for $L\circ L'$

For clarity, automata are assumed deterministic and possibly incomplete in the question and this answer. A trim automaton is incomplete unless it is empty or it accepts all strings. As your argument ...
• 39k

### Can you enumerate the set of all words over a finite alphabet?

I think that the original poster wanted to point out that lexicographic order does not work for the purpose of enumerating all words. 1 11 111 1111 ... and you never reach 2 (and you miss 0). Of ...
Let $L \subseteq \{ a, b\}^*$ be a language with one Myhill-Nerode equivalence class. You can show that $L$ must be trivial, that is $L\in \{\emptyset, \{a, b\}^*\}$, either by using the Myhill-Nerode ...